{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# `Nuqleon.Linq.CompilerServices`\n",
        "\n",
        "Provides expression tree utilities such as visitors, analyzers, rewriters, evaluators, and more."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Reference the library"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Option 1 - Use a local build\n",
        "\n",
        "If you have built the library locally, run the following cell to load the latest build."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "#r \"bin/Debug/net6.0/Nuqleon.Linq.CompilerServices.dll\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Option 2 - Use NuGet packages\n",
        "\n",
        "If you want to use the latest published package from NuGet, run the following cell."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "#r \"nuget:Nuqleon.Linq.CompilerServices,*-*\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## (Optional) Attach a debugger\n",
        "\n",
        "If you'd like to step through the source code of the library while running samples, run the following cell, and follow instructions to start a debugger (e.g. Visual Studio). Navigate to the source code of the library to set breakpoints."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "System.Diagnostics.Debugger.Launch();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Visitors\n",
        "\n",
        "`System.Linq.Expressions` comes with a default `ExpressionVisitor` that visits all nodes of an expression tree and invokes the `Update` method on a node if any of its children changes (as tested by an reference equality check). This library provides additional types of visitors to enable rewrites of expressions to other types, to track scope information of variables, to visit other elements of the tree (such as reflection information), etc.\n",
        "\n",
        "There are too many visitor types to demonstrate here, so we'll start by providing a small list and zoom in to a few of them in the sections below.\n",
        "\n",
        "* `ExpressionVisitor<TExpression>` and related types visit an `Expression` but convert it to a `TExpression`. To do so, one implements a bunch of `Make` abstract methods, e.g. `MakeBinary` given the result of recursively converting `Left`, `Right`, etc.\n",
        "* `ExpressionVisitorNarrow<...>` implements a generic visitor by overriding all of the `Make` methods for statement trees (e.g. `Block`, `Loop`, etc.) as throwing `NotSupportedException`.\n",
        "* `PartialExpressionVisitor<TExpression>` implements a generic visitor by overriding all of the `Make` methods as throwing `NotSupportedException`. Users can override the nodes they want to support.\n",
        "* `ExpressionVisitorWithReflection` is like an `ExpressionVisitor` but it also provides virtual methods that visit the reflection objects that occur in trees, e.g. `MethodInfo` on a `Call` node.\n",
        "* `CooperativeExpressionVisitor` supports dispatching to custom visitor logic when encountering a member that has a `[Visitor]` attribute applied to it.\n",
        "* `ScopedExpressionVisitor<TState>` visits an expression tree while providing ways to track declaration and use sites of `ParameterExpression` nodes.\n",
        "\n",
        "Let's zoom in to a few of these."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `ExpressionVisitorWithReflection`\n",
        "\n",
        "In the sample below, we harvest all of the `MethodInfo` objects that occur in an expression tree."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.String ToLower()\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.String Substring(Int32, Int32)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.Linq.CompilerServices;\n",
        "using System.Linq.Expressions;\n",
        "using System.Reflection;\n",
        "\n",
        "class HarvestMethods : ExpressionVisitorWithReflection\n",
        "{\n",
        "    public HashSet<MethodInfo> Methods { get; } = new();\n",
        "\n",
        "    protected override MethodInfo VisitMethod(MethodInfo method)\n",
        "    {\n",
        "        Methods.Add(method);\n",
        "\n",
        "        return method;\n",
        "    }\n",
        "}\n",
        "\n",
        "Expression<Func<string, int>> f = s => s.ToLower().Substring(1, 2).Length;\n",
        "\n",
        "var harvester = new HarvestMethods();\n",
        "\n",
        "harvester.Visit(f);\n",
        "\n",
        "foreach (var method in harvester.Methods)\n",
        "{\n",
        "    Console.WriteLine(method);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `CooperativeExpressionVisitor`\n",
        "\n",
        "Cooperative expression visitors enable dispatching into a user-specified visitor for nodes that refer to methods, properties, fields, or constructors. The benefit of this approach is to avoid centralizing the knowledge of analysis or rewrite rules in a centralized visitor.\n",
        "\n",
        "As an example, we'll try to optimize an expression containing calls to methods that are annotated with a cooperative visitor that knows how to perform local optimizations. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => 42\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "static class Sample\n",
        "{\n",
        "    [Visitor(typeof(AbsVisitor))]\n",
        "    public static long Abs(long x) => x < 0 ? -x : x;\n",
        "\n",
        "    private sealed class AbsVisitor : IRecursiveExpressionVisitor\n",
        "    {\n",
        "        public bool TryVisit(Expression expression, Func<Expression, Expression> visit, out Expression result)\n",
        "        {\n",
        "            var method = (MethodCallExpression)expression;\n",
        "\n",
        "            if (method.GetArgument(0) is ConstantExpression c && c.Value is long x)\n",
        "            {\n",
        "                result = Expression.Constant(Sample.Abs(x));\n",
        "                return true;\n",
        "            }\n",
        "\n",
        "            result = null;\n",
        "            return false;\n",
        "        }\n",
        "    }\n",
        "}\n",
        "\n",
        "Expression<Func<long>> f = () => Sample.Abs(-42);\n",
        "\n",
        "var visitor = new CooperativeExpressionVisitor();\n",
        "\n",
        "Expression res = visitor.Visit(f);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `ScopedExpressionVisitor<TState>`\n",
        "\n",
        "A scoped expression visitor keeps a map of `ParameterExpression` to `TState` values for each declaration site of a variable, e.g. in `LambdaExpression.Parameters`, `BlockExpression.Variables`, and `CatchBlock.Variable`. Upon encountering a use site of a variable, this state can be looked up. This utility enabled building visitors that deal with binding of variables or that analyze declared variables and their scopes.\n",
        "\n",
        "In the code below, we'll build a scope tracking visitor to find unbound variables in an expression `(int x) => x + y`. In this example, `x` has a declaration and a use site, but `y` does only have a use site, and is thus considered unbound."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class FindUnboundVariables : ScopedExpressionVisitor<ValueTuple>\n",
        "{\n",
        "    public HashSet<ParameterExpression> UnboundVariables { get; } = new();\n",
        "\n",
        "    protected override ValueTuple GetState(ParameterExpression variable) => default;\n",
        "\n",
        "    protected override Expression VisitParameter(ParameterExpression node)\n",
        "    {\n",
        "        if (!TryLookup(node, out var ignored))\n",
        "        {\n",
        "            UnboundVariables.Add(node);\n",
        "        }\n",
        "\n",
        "        return node;\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that we don't care about associating some value (of type `TState`) with each declared variable. Instead, we're just interested to figure out whether a variable is defined or not. As such, we use a dummy empty `ValueTuple` type. In order to figure out whether we saw a variable in a declaration site when encountering a use site, we use the `TryLookup` method in `VisitParameter`. In case we didn't find a declaration for the variable, we consider it to be unbound and add it to `UnboundVariables`.\n",
        "\n",
        "Next, we'll craft the expression `(int x) => x + y` using the `Expression` factory methods."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => (x + y)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var x = Expression.Parameter(typeof(int), \"x\");\n",
        "var y = Expression.Parameter(typeof(int), \"y\");\n",
        "\n",
        "var expr = Expression.Lambda<Func<int, int>>(Expression.Add(x, y), x);\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, let's use our utility to visit the expression and consult the `UnboundVariables` collection."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Unbound variables in `x => (x + y)` = { y }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var fuv = new FindUnboundVariables();\n",
        "\n",
        "fuv.Visit(expr);\n",
        "\n",
        "Console.WriteLine($\"Unbound variables in `{expr}` = {{ {string.Join(\", \", fuv.UnboundVariables)} }}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## `FuncletExpression`\n",
        "\n",
        "The `FuncletExpression` is a custom `Expression` node that represents a subexpression that can be partially evaluated. Expression visitors that are aware of `FuncletExpression` nodes can retain them in an expression tree, but any other expression visitor will cause a reduction of the node to a `ConstantExpression` by triggering evaluation of the `FuncletExpression`.\n",
        "\n",
        "As an example, consider an expression tree visitor for math operations that only retains simple unary and binary arithmetic operations, as well as constants and default values. Any other expression will be turned into a `FuncletExpression`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "First, we'll create an expression to operate on."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((ArrayLength(Empty()) * \"foo\".Length) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int>> f = () => Array.Empty<int>().Length * \"foo\".Length + 3;\n",
        "\n",
        "var expr = f.Body;\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In here, `Array.Empty<int>().Length` and `\"bar\".Length` are expressions that cannot be evaluated by a math engine, so we'd like to reduce them to a `ConstantExpression` by causing partial evaluation at some point in time. This can be achieved by wrapping the node with a `FuncletExpression`. To do so, let's write a visitor that retains only nodes of supported types, but wraps all the other ones with a `FuncletExpression`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class ArithOnlyVisitor : ExpressionVisitor\n",
        "{\n",
        "    public override Expression Visit(Expression node) =>\n",
        "        node switch\n",
        "        {\n",
        "            null => null,\n",
        "            _ when node.NodeType is\n",
        "                ExpressionType.Constant or\n",
        "                ExpressionType.Default\n",
        "                    => node,\n",
        "            _ when node.NodeType is\n",
        "                ExpressionType.Add or\n",
        "                ExpressionType.AddChecked or\n",
        "                ExpressionType.Divide or\n",
        "                ExpressionType.Modulo or\n",
        "                ExpressionType.Multiply or\n",
        "                ExpressionType.MultiplyChecked or\n",
        "                ExpressionType.Negate or\n",
        "                ExpressionType.NegateChecked or\n",
        "                ExpressionType.Subtract or\n",
        "                ExpressionType.SubtractChecked or\n",
        "                ExpressionType.UnaryPlus\n",
        "                    => base.Visit(node),\n",
        "            _ => FuncletExpression.Create(node)\n",
        "        };\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we're ready to run our expression through the visitor and observe `Array.Empty<int>().Length` and `\"bar\".Length` getting wrapped in a `FuncletExpression` node."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((Eval(ArrayLength(Empty())) * Eval(\"foo\".Length)) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var res = new ArithOnlyVisitor().Visit(expr);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that evaluation has not taken place yet. Expression visitors that are aware of `FuncletExpression` nodes can choose to defer or avoid reducing them. An example could be an arithmetic optimizer, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class ArithOptimizer : ExpressionVisitor\n",
        "{\n",
        "    protected override Expression VisitBinary(BinaryExpression node)\n",
        "    {\n",
        "        if (node.Type == typeof(int) && node.Conversion == null && node.Method == null)\n",
        "        {\n",
        "            if (node.NodeType is ExpressionType.Multiply or ExpressionType.MultiplyChecked)\n",
        "            {\n",
        "                var left = Visit(node.Left);\n",
        "\n",
        "                if (left is ConstantExpression leftConst)\n",
        "                {\n",
        "                    switch ((int)leftConst.Value)\n",
        "                    {\n",
        "                        case 0: // 0 * right = 0\n",
        "                            return leftConst;\n",
        "                        case 1: // 1 * right = right\n",
        "                            return Visit(node.Right);\n",
        "                    }\n",
        "                }\n",
        "\n",
        "                var right = Visit(node.Right);\n",
        "\n",
        "                if (right is ConstantExpression rightConst)\n",
        "                {\n",
        "                    switch ((int)rightConst.Value)\n",
        "                    {\n",
        "                        case 0: // left * 0 = 0\n",
        "                            return rightConst;\n",
        "                        case 1: // left * 1 = left\n",
        "                            return left;\n",
        "                    }\n",
        "                }\n",
        "\n",
        "                return node.Update(left, conversion: null, right);\n",
        "            }\n",
        "            else if (node.NodeType is ExpressionType.Add or ExpressionType.AddChecked)\n",
        "            {\n",
        "                var left = Visit(node.Left);\n",
        "\n",
        "                if (left is ConstantExpression leftConst && (int)leftConst.Value == 0) // 0 + right = right\n",
        "                {\n",
        "                    return Visit(node.Right);\n",
        "                }\n",
        "\n",
        "                var right = Visit(node.Right);\n",
        "\n",
        "                if (right is ConstantExpression rightConst && (int)rightConst.Value == 0) // left + 0 = left\n",
        "                {\n",
        "                    return left;\n",
        "                }\n",
        "\n",
        "                return node.Update(left, conversion: null, right);\n",
        "            }\n",
        "\n",
        "            // Omitted similar optimizations for other operations such as Divide, Modulo, Subtract, etc.\n",
        "        }\n",
        "\n",
        "        return base.VisitBinary(node);\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We've omitted many arithmetic rules here, but just enough to demonstrate the point. When the optimizer visits the following node:\n",
        "\n",
        "```\n",
        "Eval(ArrayLength(Empty())) * Eval(\"foo\".Length)\n",
        "```\n",
        "\n",
        "it will enter the `Multiply` branch and start by visiting the `Left` node, which corresponds to:\n",
        "\n",
        "```\n",
        "Eval(ArrayLength(Empty()))\n",
        "```\n",
        "\n",
        "Visiting a `FuncletExpression` node causes partial evaluation, which in this case will result in a `ConstantExpression` with value `0`. The optimizer then detects this particular case to reduce `0 * anything` to `0`, using the rules of multiplication. As such, it avoids evaluating `\"bar\".Length` entirely.\n",
        "\n",
        "**Note:** Obviously this may take away side-effects which would otherwise occur. A proper conservative optimizer for a language with side-effects would avoid making such rewrites unless it knows that `Right` has no observable side-effects. The optimizer in `Nuqleon.Linq.Expressions.Optimizers` does operate in such a manner."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "3\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var opt = new ArithOptimizer().Visit(res);\n",
        "\n",
        "Console.WriteLine(opt);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Expression tree factories\n",
        "\n",
        "The `IExpressionFactory` abstracts over the factory methods found on `Expression` and allows for custom implementations that can inject various behaviors. For example, a custom factory could return cached shared nodes for various invocations, perform additional forms of type checking, etc.\n",
        "\n",
        "A first implementation of `IExpressionFactory` is `ExpressionFactory` which simply calls the corresponding factory methods on `Expression`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(x + 1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "IExpressionFactory exprFactory = ExpressionFactory.Instance;\n",
        "\n",
        "var expr = exprFactory.Add(exprFactory.Parameter(typeof(int), \"x\"), exprFactory.Constant(1));\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Another implementation of `IExpressionFactory` is `ExpressionUnsafeFactory` which bypasses various type checks that occur in `Expression` factory methods and can be used for expression deserializers. This can provide a significant speedup. To illustrate this, let's define a small benchmark that constructs a `MethodCallExpression` which requires reflection calls to perform type checking on the object and arguments for the method being called.\n",
        "\n",
        "To define the benchmark, we'll leverage the facilities in `Nuqleon.Time` to build stopwatches to measure time and memory allocations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Time;\n",
        "\n",
        "class MemoryClock : IClock\n",
        "{\n",
        "    public long Now => GC.GetAllocatedBytesForCurrentThread();\n",
        "}\n",
        "\n",
        "IStopwatch swMem = StopwatchFactory.FromClock(new MemoryClock()).Create();\n",
        "IStopwatch swTime = StopwatchFactory.Diagnostics.Create();\n",
        "\n",
        "void Benchmark(string title, Action test, int n)\n",
        "{\n",
        "    swMem.Restart();\n",
        "    swTime.Restart();\n",
        "\n",
        "    for (int i = 0; i < n; i++)\n",
        "    {\n",
        "        test();\n",
        "    }\n",
        "\n",
        "    swTime.Stop();\n",
        "    swMem.Stop();\n",
        "\n",
        "    Console.WriteLine($\"{title} completed in {swTime.ElapsedMilliseconds} ms and allocated {swMem.ElapsedTicks} bytes.\");\n",
        "}\n",
        "\n",
        "// The core benchmark that constructs expression trees.\n",
        "\n",
        "var mtd = typeof(string).GetMethod(nameof(string.Substring), new[] { typeof(int), typeof(int) });\n",
        "\n",
        "void Benchmark(string title, IExpressionFactory factory, int n)\n",
        "{\n",
        "    Benchmark(title, () => factory.Call(factory.Constant(\"bar\"), mtd, factory.Constant(1), factory.Constant(2)), n);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we're ready to invoke this benchmark to compare the regular and the unsafe expression factory."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Default completed in 253 ms and allocated 168000528 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Unsafe completed in 74 ms and allocated 168008560 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "IExpressionFactory defaultFactory = ExpressionFactory.Instance;\n",
        "IExpressionFactory unsafeFactory = ExpressionUnsafeFactory.Instance;\n",
        "\n",
        "Benchmark(\"Default\", ExpressionFactory.Instance, 1_000_000);\n",
        "Benchmark(\"Unsafe\", ExpressionUnsafeFactory.Instance, 1_000_000);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the execution time for the unsafe factory is lower than for the regular factory which has to perform a lot of type checks. However, memory cost is identical, in part due to the `Expression` factory methods maintaining an internal cache of `ParameterInfo[]` arrays obtained from calling `GetParameters()` on the `MethodInfo` during the type checking of the `Arguments` provided to `Call`. Despite this caching, there are still many corners of the `Expression` factories where expensive operations and sometimes allocations take place.\n",
        "\n",
        "In the context of a trusted subsystem where (a lot of) expression trees get serialized and deserialized, bypassing the type checking can be beneficial. If the original expression, prior to serialization, did type check correctly, and we can guarantee that any types and members referenced in these expressions did not change, then the expression should still type check at the point of deserialization. This is one of the optimizations that have been used in high-density Reaqtor deployments where we recover millions of expression trees containing hundreds of nodes each. The savings achieved can add up to significantly reduce recovery times, during which event processing is stalled."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Because the expression factories implement all factory methods as `virtual`, we can also derive from the factories to add additional optimizations, e.g. caching of `Constant` or `Default` nodes to reduce the number of allocations. We illustrate this below using the `Nuqleon.Memory` faciltities for function memoization."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "class ExpressionFactoryWithCaching : ExpressionFactory, IClearable\n",
        "{\n",
        "    private readonly IMemoizedDelegate<Func<object, Type, ConstantExpression>> _makeConstant;\n",
        "    private readonly IMemoizedDelegate<Func<Type, DefaultExpression>> _makeDefault;\n",
        "\n",
        "    public ExpressionFactoryWithCaching(IMemoizer memoizer)\n",
        "    {\n",
        "        _makeConstant = memoizer.Memoize<object, Type, ConstantExpression>((value, type) => base.Constant(value, type));\n",
        "        _makeDefault = memoizer.Memoize<Type, DefaultExpression>(type => base.Default(type));\n",
        "    }\n",
        "\n",
        "    public override ConstantExpression Constant(object value) => Constant(value, value?.GetType() ?? typeof(object));\n",
        "\n",
        "    public override ConstantExpression Constant(object value, Type type) => _makeConstant.Delegate(value, type);\n",
        "\n",
        "    public override DefaultExpression Default(Type type) => _makeDefault.Delegate(type);\n",
        "\n",
        "    public void Clear()\n",
        "    {\n",
        "        _makeConstant.Cache.Clear();\n",
        "        _makeDefault.Cache.Clear();\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we can create an instance of `ExpressionFactoryWithCaching` and observe the effects of caching."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var mem = Memoizer.Create(MemoizationCacheFactory.Unbounded);\n",
        "\n",
        "var factory = new ExpressionFactoryWithCaching(mem);\n",
        "\n",
        "var const1 = factory.Constant(42);\n",
        "var const2 = factory.Constant(42);\n",
        "\n",
        "Console.WriteLine(object.ReferenceEquals(const1, const2));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Expression tree analysis\n",
        "\n",
        "Various utilities are provided in this library to make the task of analyzing expression trees easier."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Equality comparers\n",
        "\n",
        "`ExpressionEqualityComparer` implements `IEqualityComparer<Expression>` to compare two `Expression` instances for equality, taking binding of variables and labels (used in `Goto` and `Label` expressions) into account. For example, given trees `x => x` and `y => y`, they will compare equal even though `x` and `y` are not reference equal. That is, as long as the binding of variables between use sites and definition sites is equivalent in both trees being compared, the equality requirement is met.\n",
        "\n",
        "An example of using comparers is shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var eq = new ExpressionEqualityComparer();\n",
        "\n",
        "Expression<Func<int, int, int>> e1 = (x, y) => x * y;\n",
        "Expression<Func<int, int, int>> e2 = (a, b) => a * b;\n",
        "\n",
        "Console.WriteLine(eq.Equals(e1, e1));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Unbound parameters do not compare equal by default."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "False\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var p1 = Expression.Parameter(typeof(int), \"x\");\n",
        "var p2 = Expression.Parameter(typeof(int), \"x\");\n",
        "\n",
        "Console.WriteLine(eq.Equals(p1, p2));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "If one wants to treat unbound parameters different, a custom `ExpressionEqualityComparator` can be built that overrides `EqualsGlobalParameter`, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class ExpressionEqualityComparatorWithGlobalVariableEqualityByName : ExpressionEqualityComparator\n",
        "{\n",
        "    protected override bool EqualsGlobalParameter(ParameterExpression left, ParameterExpression right) => left.Type == right.Type && left.Name == right.Name;\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "`ExpressionEqualityComparer` provides an equality compararer by wrapping a factory for `ExpressionEqualityComparator` instances. The latter are stateful because they have to keep track of environments, i.e. the variables and labels that are declarated within the tree, in order to perform binding. To use our custom `ExpressionEqualityComparatorWithGlobalVariableEqualityByName`, we can wrap it as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var eq = new ExpressionEqualityComparer(() => new ExpressionEqualityComparatorWithGlobalVariableEqualityByName());\n",
        "\n",
        "var p1 = Expression.Parameter(typeof(int), \"x\");\n",
        "var p2 = Expression.Parameter(typeof(int), \"x\");\n",
        "\n",
        "Console.WriteLine(eq.Equals(p1, p2));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This time around, the global parameters are considered to be equal. We use this technique in Reaqtor to compare expressions for equality prior to performing binding operations."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Free variable scanner\n",
        "\n",
        "We've already built a free variable scanner manually earlier in this notebook, but the library comes with such a facility built-in. As an example, consider an expression of the form `x => x + y` where `y` is unbound."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => (x + y)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var x = Expression.Parameter(typeof(int), \"x\");\n",
        "var y = Expression.Parameter(typeof(int), \"y\");\n",
        "\n",
        "var expr = Expression.Lambda<Func<int, int>>(Expression.Add(x, y), x);\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can now use `FreeVariableScanner` to determine whether the expression contains any free variables, or to get a list of such variables. Note that the former operation is more efficient than getting all the unbound variables and performing an `Any()` or `Count() > 0` check, because we don't have to allocate a collection."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Has free variables = True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Free variables = { y }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine($\"Has free variables = {FreeVariableScanner.HasFreeVariables(expr)}\");\n",
        "Console.WriteLine($\"Free variables = {{ {string.Join(\", \", FreeVariableScanner.Scan(expr))} }}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Allow list scanner\n",
        "\n",
        "When processing expressions, it's often useful to scan them for undesirable operations, such as calls to methods that are unsafe to the hosting environment (when evaluating an expression) or constructs that cannot be translated to some target language (e.g. when writing a query provider). This library provides allow list scanners that check expressions against a given list of allowed items. Two different types are provided:\n",
        "\n",
        "* `ExpressionTypeAllowListScanner` which checks the `Type` for every `Expression` node in a given expression tree, e.g. to make sure a tree evaluates within a certain \"type domain\";\n",
        "* `ExpressionMemberAllowListScanner` which checks occurrences of any `MemberInfo` on any `Expression` node in a given exprssion tree, e.g. to check for methods, properties, fields, and constructors used.\n",
        "\n",
        "Let's first have a look at these utilities."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "First, we'll explore a trivial `ExpressionTypeAllowListScanner` that only allows expressions that use `int`-based operations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(1 + 2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var typeScanner = new ExpressionTypeAllowListScanner\n",
        "{\n",
        "    Types = { typeof(int) }\n",
        "};\n",
        "\n",
        "var validExpr = Expression.Add(Expression.Constant(1), Expression.Constant(2));\n",
        "\n",
        "var res = typeScanner.Visit(validExpr);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In case the tree contains operations involving other types, it gets rejected."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.NotSupportedException: Expression '\"foo\"' uses 'string' which is not allowed.\r\n   at System.Linq.CompilerServices.ExpressionTypeAllowListScannerBase.ResolveExpression[T](T expression, Type type, Func`2 visit) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionTypeAllowListScannerBase.cs:line 59\r\n   at System.Linq.CompilerServices.ExpressionTypeAllowListScannerBase.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionTypeAllowListScannerBase.cs:line 33\r\n   at System.Linq.Expressions.ExpressionVisitor.VisitMember(MemberExpression node)\r\n   at System.Linq.Expressions.MemberExpression.Accept(ExpressionVisitor visitor)\r\n   at System.Linq.Expressions.ExpressionVisitor.Visit(Expression node)\r\n   at System.Linq.CompilerServices.ExpressionTypeAllowListScannerBase.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionTypeAllowListScannerBase.cs:line 37\r\n   at System.Linq.Expressions.ExpressionVisitor.VisitBinary(BinaryExpression node)\r\n   at System.Linq.Expressions.BinaryExpression.Accept(ExpressionVisitor visitor)\r\n   at System.Linq.Expressions.ExpressionVisitor.Visit(Expression node)\r\n   at System.Linq.CompilerServices.ExpressionTypeAllowListScannerBase.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionTypeAllowListScannerBase.cs:line 37\r\n   at Submission#27.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var invalidExpr = Expression.Add(Expression.Constant(1), Expression.Property(Expression.Constant(\"foo\"), nameof(string.Length)));\n",
        "\n",
        "var res = typeScanner.Visit(invalidExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In case it's desirable to handle expressions that don't pass the allowlist rules, one can override `ResolveExpression` as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(1 + Eval(\"foo\").Length)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "class MyExpressionTypeAllowListScanner : ExpressionTypeAllowListScanner\n",
        "{\n",
        "    protected override Expression ResolveExpression<T>(T expression, Type type, Func<T, Expression> visit) => FuncletExpression.Create(expression);\n",
        "}\n",
        "\n",
        "var myTypeScanner = new MyExpressionTypeAllowListScanner\n",
        "{\n",
        "    Types = { typeof(int) }\n",
        "};\n",
        "\n",
        "var res = myTypeScanner.Visit(invalidExpr);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In this example we use the sledgehammer of wrapping the rejected expression in a funclet, which will cause partial evaluation down the line. For example, prior to submitting an expression to a remote service, partial evaluation of any unsupported constructs can take place locally. A better example may be using a member-based allow list scanner, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => Abs((x + 1))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var memberScanner = new ExpressionMemberAllowListScanner\n",
        "{\n",
        "    Members =\n",
        "    {\n",
        "        typeof(Math).GetMethod(nameof(Math.Abs), new[] { typeof(int) })\n",
        "    }\n",
        "};\n",
        "\n",
        "Expression<Func<int, int>> f = x => Math.Abs(x + 1);\n",
        "\n",
        "var res = memberScanner.Visit(f);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Here, we allow uses of `Math.Abs(int)`, but nothing else. Alternatively, we could have added `typeof(Abs)` to the `DeclaringTypes` collection on the scanner, to allow all members on `Math`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now, let's consider a more complex expression that refers to a variable in the outer scope. This causes the creation of a closure, which will manifest itself in the expression tree as a field lookup using a `MemberExpression`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => Abs((x + value(Submission#30).y))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "int y = 1;\n",
        "Expression<Func<int, int>> fWithClosure = x => Math.Abs(x + y);\n",
        "\n",
        "Console.WriteLine(fWithClosure);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This field lookup on the compiler-generated closure object is not present in the allow list, so the scanner will reject it."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.NotSupportedException: Expression '__c0.y' uses 'int Submission#30.y' which is not allowed.\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.ResolveExpression[T](T expression, MemberInfo member, Func`2 visit) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 156\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.CheckExpression[T](T expression, MemberInfo member, Func`2 visit) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 96\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.VisitMember(MemberExpression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 58\r\n   at System.Linq.Expressions.MemberExpression.Accept(ExpressionVisitor visitor)\r\n   at System.Linq.Expressions.ExpressionVisitor.VisitBinary(BinaryExpression node)\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.CheckExpression[T](T expression, MemberInfo member, Func`2 visit) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 100\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.VisitBinary(BinaryExpression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 30\r\n   at System.Linq.Expressions.BinaryExpression.Accept(ExpressionVisitor visitor)\r\n   at System.Dynamic.Utils.ExpressionVisitorUtils.VisitArguments(ExpressionVisitor visitor, IArgumentProvider nodes)\r\n   at System.Linq.Expressions.ExpressionVisitor.VisitMethodCall(MethodCallExpression node)\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.CheckExpression[T](T expression, MemberInfo member, Func`2 visit) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 100\r\n   at System.Linq.CompilerServices.ExpressionMemberAllowListScannerBase.VisitMethodCall(MethodCallExpression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Analysis\\ExpressionMemberAllowListScannerBase.cs:line 65\r\n   at System.Linq.Expressions.MethodCallExpression.Accept(ExpressionVisitor visitor)\r\n   at System.Linq.Expressions.ExpressionVisitor.VisitLambda[T](Expression`1 node)\r\n   at Submission#31.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var res = memberScanner.Visit(fWithClosure);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can now build a custom scanner type that uses a funclet to trigger partial evaluation of unsupported nodes. In this case, it will cause reduction of the closure access to a `ConstantExpression`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => Abs((x + Eval(value(Submission#30).y)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "class MyExpressionMemberAllowListScanner : ExpressionMemberAllowListScanner\n",
        "{\n",
        "    protected override Expression ResolveExpression<T>(T expression, MemberInfo member, Func<T, Expression> visit) => FuncletExpression.Create(expression);\n",
        "}\n",
        "\n",
        "var myMemberScanner = new MyExpressionMemberAllowListScanner\n",
        "{\n",
        "    Members =\n",
        "    {\n",
        "        typeof(Math).GetMethod(nameof(Math.Abs), new[] { typeof(int) })\n",
        "    }\n",
        "};\n",
        "\n",
        "var res = myMemberScanner.Visit(fWithClosure);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To illustrate the partial evaluation carried out by the `FuncletExpression`, we can simply run an `ExpressionVisitor` over the expression, which will trigger calls to `Reduce`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => Abs((x + 1))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "class ReduceExpressionVisitor : ExpressionVisitor\n",
        "{\n",
        "}\n",
        "\n",
        "var reduced = new ReduceExpressionVisitor().Visit(res);\n",
        "\n",
        "Console.WriteLine(reduced);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "More advanced uses of type-based and member-based allow list scanners can be constructed by deriving from the `ExpressionTypeAllowListScannerBase` and `ExpressionTypeAllowMemberScannerBase` classes instead. These provide `Check` methods that are used to check whether a type or member is allowed to be used. These predicates can be arbitrary rather than type-based. For example, one could allow any type or member in a particular assembly."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Expression tree rewriters\n",
        "\n",
        "This library also provides a whole plethora of expression tree rewriting utilities."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Alpha renaming\n",
        "\n",
        "Lambda calculus has the notion of alpha renaming whereby the names of variables get changed in a way that doesn't inadvertently changes the bindings of variable. For example, consider an expression `x => y => x + y`. In here, we can change the name of `x` to `a` but not to `y` because it'd cause the binding to change to the `y` declared on the inner lambda expression.\n",
        "\n",
        "This library provides an implementation of alpha renaming using the `AlphaRenamer.EliminateNameConflicts` static method, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => x => x\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "x => x => x\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var x0 = Expression.Parameter(typeof(int), \"x\");\n",
        "var x1 = Expression.Parameter(typeof(int), \"x\");\n",
        "\n",
        "var ambiguousNames1 = Expression.Lambda(Expression.Lambda(x0, x0), x0);\n",
        "var ambiguousNames2 = Expression.Lambda(Expression.Lambda(x0, x1), x1);\n",
        "\n",
        "Console.WriteLine(ambiguousNames1);\n",
        "Console.WriteLine(ambiguousNames2);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Both functions have different meanings. The first one is equivalent to `_ => x => x`, because the use site of `x` in the inner lambda binds to the declaration site of `x` as a parameter on the inner lambda. The second one is equivalent to `x => _ => x`.\n",
        "\n",
        "Alpha renaming gets rid of the syntactic ambiguity by creating new `ParameterExpression` nodes with unique names."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => x0 => x0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "x => x0 => x\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var uniqueNames1 = AlphaRenamer.EliminateNameConflicts(ambiguousNames1);\n",
        "var uniqueNames2 = AlphaRenamer.EliminateNameConflicts(ambiguousNames2);\n",
        "\n",
        "Console.WriteLine(uniqueNames1);\n",
        "Console.WriteLine(uniqueNames2);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Beta reduction\n",
        "\n",
        "Computation in lambda calculus is driven by beta reduction. Given an invocation of a lambda expression, a reduction can be made by substituting the arguments used in the invocation for the parameters of the lambda expression. For example:\n",
        "\n",
        "```csharp\n",
        "(x => x + 1)(2)\n",
        "```\n",
        "\n",
        "can be reduced to `2 + 1` by substituting `2` for `x` in the body of the lambda expression. That is, arguments get inlined in the lambda body.\n",
        "\n",
        "Let's first translate this example to expression trees, as follows:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(x => (x + 1), 2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int, int>> f = x => x + 1;\n",
        "\n",
        "var expr = Expression.Invoke(f, Expression.Constant(2));\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can now use the `BetaReducer` in this library to reduce the expression to `2 + 1`, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(2 + 1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var reduced = BetaReducer.Reduce(expr);\n",
        "\n",
        "Console.WriteLine(reduced);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The call to `Reduce` does find any `Invoke(Lambda(...), ...)` structure in the given expression tree and attempts to reduce it. Given that beta reduction is a very essential technique employed by Reaqtor to bind reactive query expressions, we'll build a slightly bigger sample below that illustrates binding and reduction."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "First, let's build a little catalog of functions for a simple math engine. We'll start by defining some operations such as `Abs` and `Pow` and put them in a dictionary."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var functions = new Dictionary<string, Expression>\n",
        "{\n",
        "    { \"abs\", (Expression<Func<double, double>>)(x => Math.Abs(x)) },\n",
        "    { \"pow\", (Expression<Func<double, double, double>>)((x, y) => Math.Pow(x, y)) },\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The goal is for users to be able to submit expressions that refer to the functions by name using unbound `ParameterExpression` nodes. For example:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(abs, -2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var expr = Expression.Invoke(Expression.Parameter(typeof(Func<double, double>), \"abs\"), Expression.Constant(-2.0));\n",
        "\n",
        "Console.WriteLine(expr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Reaqtor uses this technique to normalize expressions submitted by client libraries. Rather than doing so for math operations, it does this for reactive query operators such as `Where`, `Select`, `Window`, etc. The normalization step takes a friendly user expression such as `xs.Where(x => x > 0)` to an expression that is no longer bound to a concrete client-side `MethodInfo` for `Where`. In our simplified math example shown here, one can image a client library that allows the user to write `calculator.Abs(-2.0)`, which gets normalized to `Invoke(Abs, -2.0)` where `Abs` is an unbound parameter expression. The calculator engine then binds the `Abs` function to a concrete implementation, e.g. using `Math.Abs`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To build a binder, we'll leverage the `FreeVariableScanner` to find all unbound parameters in the expression submitted by the user, and then build a binding expression around it. Let's do these things one step at a time and start by scanning the free variables."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "abs\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var freeVars = FreeVariableScanner.Scan(expr);\n",
        "\n",
        "Console.WriteLine(string.Join(\", \", freeVars));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, we can perform a technique called *lambda lifting* to wrap the user expression in a lambda that has all of the unbound variables as parameters. This is shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "abs => Invoke(abs, -2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var lambda = Expression.Lambda(expr, freeVars);\n",
        "\n",
        "Console.WriteLine(lambda);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To perform binding, we can now look up all of the unbound parameters in our `functions` registry and construct an `InvocationExpression` around the lambda that was built above."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(abs => Invoke(abs, -2), x => Abs(x))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var bound = Expression.Invoke(lambda, freeVars.Select(freeVar => functions[freeVar.Name]));\n",
        "\n",
        "Console.WriteLine(bound);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that expression factories perform rigorous type checking, so if the user's expression is trying to invoke `abs` using `int` operands, the binding step above would fail. Similarly, binding would fail if we don't find a particular variable in the `function` registry.\n",
        "\n",
        "At this point, we could already evaluate the user's expression. For this, we'll make use of the `Evaluate` extension method provided by this library (discussed further on in this notebook)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "2\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(bound.Evaluate<double>());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "However, this can be rather inefficient because the compiled expression tree can be simplified by applying beta reduction steps first. This can also help with debugging, size of expressions stored, etc. So, let's give beta reduction a try."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(abs => Invoke(abs, -2), x => Abs(x))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var reduced = BetaReducer.Reduce(bound);\n",
        "\n",
        "Console.WriteLine(reduced);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This didn't work because the `BetaReducer` is very conservative when it comes to inlining non-trivial expressions which may cause reordering of side-effects. To override this behavior, we can use an overload of `Reduce`, as shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(x => Abs(x), -2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var reduced = BetaReducer.Reduce(bound, BetaReductionNodeTypes.Unrestricted, BetaReductionRestrictions.None);\n",
        "\n",
        "Console.WriteLine(reduced);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A detailed description of these parameters is outside the scope of this notebook, but a little brainteaser is shown below to point out the potential evils of performing beta reduction.\n",
        "\n",
        "```csharp\n",
        "(s => Console.ReadLine() + s + s)(Console.ReadLine())\n",
        "```\n",
        "\n",
        "When evaluating this code, the user will get two prompts to input a string. Say the user enters `bar` and `foo`, then the result will be `foobarbar`. If \"naive\" unrestricted beta reduction is carried out, we can end up with the following:\n",
        "\n",
        "```csharp\n",
        "Console.ReadLine() + Console.ReadLine() + Console.ReadLine()\n",
        "```\n",
        "\n",
        "which prompts the user for three inputs. If the user enters `bar`, `foo`, and `qux`, the result will be `barfooqux`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Continuing with our running example, note that the resutling expression is not fully reduced yet. In particular, we still have an `InvocationExpression` node left in the tree. To cause further reduction, we can use the `ReduceEager` method which carries out a *fixed point* loop around the core beta reduction logic. That is, it keeps applying beta reduction until the tree no longer changes. An example is shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Abs(-2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var reduced = BetaReducer.ReduceEager(bound, BetaReductionNodeTypes.Unrestricted, BetaReductionRestrictions.None, throwOnCycle: true);\n",
        "\n",
        "Console.WriteLine(reduced);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In many cases, binding and beta reduction needs to be carried out in a *fixed loop* algorithm, because definitions may refer to other definitions. As an example, consider adding a `GetRadius` function that's built on top of `Pow` and `Sqrt`. Let's add a few definitions to our `functions` registry."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "functions.Add(\"sqrt\", (Expression<Func<double, double>>)(x => Math.Sqrt(x)));\n",
        "\n",
        "var x = Expression.Parameter(typeof(double), \"x\");\n",
        "var y = Expression.Parameter(typeof(double), \"y\");\n",
        "\n",
        "var sqrt = Expression.Parameter(typeof(Func<double, double>), \"sqrt\");\n",
        "var pow = Expression.Parameter(typeof(Func<double, double, double>), \"pow\");\n",
        "var two = Expression.Constant(2.0);\n",
        "\n",
        "var getRadius = Expression.Lambda(Expression.Invoke(sqrt, Expression.Add(Expression.Invoke(pow, x, two), Expression.Invoke(pow, y, two))), x, y);\n",
        "\n",
        "functions.Add(\"getRadius\", getRadius);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's now create a reusable `Bind` function, encapsulating the logic we used before, but adding a `bool` return type to indicate whether any binding took place."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "bool Bind(Expression expr, out Expression bound)\n",
        "{\n",
        "    var freeVars = FreeVariableScanner.Scan(expr);\n",
        "\n",
        "    if (freeVars.Count() == 0)\n",
        "    {\n",
        "        bound = expr;\n",
        "        return false;\n",
        "    }\n",
        "\n",
        "    var lambda = Expression.Lambda(expr, freeVars);\n",
        "    \n",
        "    bound = Expression.Invoke(lambda, freeVars.Select(freeVar => functions[freeVar.Name]));\n",
        "    return true;\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's also encapsulate our beta reduction logic in a `Reduce` method."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static Expression Reduce(Expression expr)\n",
        "{\n",
        "    var reduced = BetaReducer.ReduceEager(expr, BetaReductionNodeTypes.Unrestricted, BetaReductionRestrictions.None, throwOnCycle: true);\n",
        "    return reduced;\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To show the effects of a single pass of binding and reduction on a user expression that refers to `GetRadius`, we'll go ahead and build a such an expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var expr = Expression.Invoke(Expression.Parameter(typeof(Func<double, double, double>), \"getRadius\"), Expression.Constant(3.0), Expression.Constant(4.0));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A single turn of the binding and reduction crank yields the following result."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke(sqrt, (Invoke(pow, 3, 2) + Invoke(pow, 4, 2)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "if (Bind(expr, out var bound))\n",
        "{\n",
        "    var res = Reduce(bound);\n",
        "    Console.WriteLine(res);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This expression cannot be evaluated yet because it now refers to `Sqrt` and `Pow`. To get to the point of evaluating the expression, we need to continue binding until no more binding steps are necessary. This can be achieved using a simple loop."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Sqrt((Pow(3, 2) + Pow(4, 2)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression BindFully(Expression expr)\n",
        "{\n",
        "    while (Bind(expr, out expr))\n",
        "    {\n",
        "        expr = Reduce(expr);\n",
        "    }\n",
        "\n",
        "    return expr;\n",
        "}\n",
        "\n",
        "var res = BindFully(expr);\n",
        "\n",
        "Console.WriteLine(res);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now the expression is fully bound to `Math.*` methods, and we can go ahead an evaluate it."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "5\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(res.Evaluate<double>());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Eta converter\n",
        "\n",
        "A final lambda calculus construct is eta conversion, which simplifies an expression of the form `(x => f(x))` to `f`, by taking away the redundant lambda \"abstraction\" whose body contains an invocation \"application\". The result is a simpler, more compact, expression. This library supports this form of simplifying expressions through `EtaConverter.Convert`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => Invoke(f, x)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "f\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var x = Expression.Parameter(typeof(int), \"x\");\n",
        "var f = Expression.Parameter(typeof(Func<int, int>), \"f\");\n",
        "\n",
        "var expr = Expression.Lambda(Expression.Invoke(f, x), x);\n",
        "\n",
        "Console.WriteLine(expr);\n",
        "\n",
        "var simpler = EtaConverter.Convert(expr);\n",
        "\n",
        "Console.WriteLine(simpler);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Compiler-generated name elimination\n",
        "\n",
        "The C# compiler emits compiler-generated names for certain lambda expression parameters, e.g. in the context of `let` clauses that introduce so-called \"transparent identifiers\". An example is shown below using `IQueryable<T>`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Int32[].Select(x => new <>f__AnonymousType0#51`2(x = x, y = (x + 1))).Select(<>h__TransparentIdentifier0 => new <>f__AnonymousType1#51`2(<>h__TransparentIdentifier0 = <>h__TransparentIdentifier0, z = (<>h__TransparentIdentifier0.y * 2))).Select(<>h__TransparentIdentifier1 => ((<>h__TransparentIdentifier1.<>h__TransparentIdentifier0.x + <>h__TransparentIdentifier1.<>h__TransparentIdentifier0.y) - <>h__TransparentIdentifier1.z))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var res = from x in new[] { 1, 2, 3 }.AsQueryable()\n",
        "          let y = x + 1\n",
        "          let z = y * 2\n",
        "          select x + y - z;\n",
        "\n",
        "Console.WriteLine(res.Expression);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The resulting expression tree shows quite verbose compiler-generated identifiers which can hamper debuggability. Using the `CompilerGeneratedNameEliminator.Prettify` utility we can rewrite the expression using simpler identifiers."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Int32[].Select(x => new <>f__AnonymousType0#51`2(x = x, y = (x + 1))).Select(t => new <>f__AnonymousType1#51`2(<>h__TransparentIdentifier0 = t, z = (t.y * 2))).Select(t => ((t.<>h__TransparentIdentifier0.x + t.<>h__TransparentIdentifier0.y) - t.z))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var pretty = CompilerGeneratedNameEliminator.Prettify(res.Expression);\n",
        "\n",
        "Console.WriteLine(pretty);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that mileage is limited because the rewriter cannot change type names; it can only change the names of `ParameterExpression` nodes."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Constant hoisting\n",
        "\n",
        "In services like Reaqtor that host and evaluate millions of expressions, it's often useful to detect expressions that are identical modulo constants. These constants may get introduced due to partial evaluation at the client side, e.g. due to closures. An example is shown below:\n",
        "\n",
        "```csharp\n",
        "int a = 41;\n",
        "\n",
        "IQueryable<int> query = from x in xs where x > a select x + 1;\n",
        "\n",
        "foreach (var x in query)\n",
        "{\n",
        "    // use results\n",
        "}\n",
        "```\n",
        "\n",
        "This query will effectively get translated to the following if closures are being eliminates (e.g. using the `FuncletExpression` approach described earlier):\n",
        "\n",
        "```csharp\n",
        "IQueryable<int> query = from x in xs where x > 42 select x + 1;\n",
        "```\n",
        "\n",
        "Other invocations of the same code may use a different value for `a` and thus generate other queries that are identical modulo this single constant:\n",
        "\n",
        "```csharp\n",
        "IQueryable<int> query1 = from x in xs where x > 41 select x + 1;\n",
        "IQueryable<int> query2 = from x in xs where x > 42 select x + 1;\n",
        "IQueryable<int> query3 = from x in xs where x > 43 select x + 1;\n",
        "```\n",
        "\n",
        "If a high-density service ends up compiling all of these query expressions in order to evaluate them, we can end up with a lot of JITted code on the heap, and pay the price for emitting the code in the first place (e.g. using `System.Reflection.Emit` under the hood). By using the technique of constant hoisting, we can lift constants out of these queries, like this:\n",
        "\n",
        "```csharp\n",
        "Func<int, int, IQueryable<int>> query = (c1, c2) => from x in xs where x > c1 select x + c2;\n",
        "\n",
        "IQueryable<int> query1 = query(41, 1);\n",
        "IQueryable<int> query2 = query(42, 1);\n",
        "IQueryable<int> query3 = query(43, 1);\n",
        "```\n",
        "\n",
        "The `ConstantHoister` in this library provides support to do this, which is shown below. First, let's write a few user queries that are identical modulo constants."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Range(1, 10).Where(x => ((x % 2) == 0)).Select(x => (x + 9))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Range(2, 20).Where(y => ((y % 3) == 1)).Select(y => (y + 8))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Range(3, 30).Where(z => ((z % 4) == 2)).Select(z => (z + 7))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<IEnumerable<int>>> query1 = () => Enumerable.Range(1, 10).Where(x => x % 2 == 0).Select(x => x + 9);\n",
        "Expression<Func<IEnumerable<int>>> query2 = () => Enumerable.Range(2, 20).Where(y => y % 3 == 1).Select(y => y + 8);\n",
        "Expression<Func<IEnumerable<int>>> query3 = () => Enumerable.Range(3, 30).Where(z => z % 4 == 2).Select(z => z + 7);\n",
        "\n",
        "Expression expr1 = query1.Body;\n",
        "Expression expr2 = query2.Body;\n",
        "Expression expr3 = query3.Body;\n",
        "\n",
        "Console.WriteLine(expr1);\n",
        "Console.WriteLine(expr2);\n",
        "Console.WriteLine(expr3);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To make our setup a little more challenging, note that we've also used different variable names in the three expressions. Modulo the constants, all the queries have the same semantics."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, let's explore the `ConstantHoister` facility to hoist out constants for these three query expressions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var hoister = new ConstantHoister();\n",
        "\n",
        "ExpressionWithEnvironment hoisted1 = hoister.Hoist(expr1);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The call to `Hoist` returns an object that contains an expression and an environment. Let's first look at the `Expression` property."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Range(@p0, @p1).Where(x => ((x % @p2) == @p3)).Select(x => (x + @p4))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(hoisted1.Expression);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that all of the `ConstantExpression` nodes have been substituted by `ParameterExpression` nodes. In other words, we end up with a parameterized query. Now, let's look at the `Environment`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "  @p0 -> 1\r\n  @p1 -> 10\r\n  @p2 -> 2\r\n  @p3 -> 0\r\n  @p4 -> 9\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var sb = new StringBuilder();\n",
        "\n",
        "foreach (var (key, value) in hoisted1.Environment)\n",
        "{\n",
        "    sb.AppendLine($\"  {key} -> {value}\");\n",
        "}\n",
        "\n",
        "Console.WriteLine(sb);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can now combine the environment and the hoisted expression to create a parameterized query."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(@p0, @p1, @p2, @p3, @p4) => Range(@p0, @p1).Where(x => ((x % @p2) == @p3)).Select(x => (x + @p4))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var constantHoistedExpr = Expression.Lambda(hoisted1.Expression, hoisted1.Environment.Select(kv => kv.Key));\n",
        "\n",
        "Console.WriteLine(constantHoistedExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The original user expression is now equivalent to invoking this query with the values in the environment, like this:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Invoke((@p0, @p1, @p2, @p3, @p4) => Range(@p0, @p1).Where(x => ((x % @p2) == @p3)).Select(x => (x + @p4)), 1, 10, 2, 0, 9)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var reconstructedQueryExpr = Expression.Invoke(constantHoistedExpr, hoisted1.Environment.Select(kv => Expression.Constant(kv.Value, kv.Key.Type)));\n",
        "\n",
        "Console.WriteLine(reconstructedQueryExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "However, we don't just want to use the `ConstantHoister` to hoist out constants just to put them back using lambda lifting, invocation, and beta reduction. Instead, we want to look up a compiled query expression from the lambda lifted query expression. To do so, let's start off by defining a compiled delegate cache as a dictionary that maps from `LambdaExpression` to `Delegate`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var compiledQueries = new Dictionary<LambdaExpression, Delegate>(new ExpressionEqualityComparer());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "By using the `ExpressionEqualityComparer`, expressions get compared using value equality semantics rather than reference equality. Note that this will also take care of query expressions being different modulo parameter names in e.g. query clauses."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, let's encapsulate our constant hoisting experiments in a single `Evaluate` function that will perform constant hoisting and lambda lifting prior to looking up whether the query has been received before through our `compiledQueries` cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "void Evaluate(Expression expression)\n",
        "{\n",
        "    var hoister = new ConstantHoister();\n",
        "\n",
        "    ExpressionWithEnvironment hoisted = hoister.Hoist(expression);\n",
        "\n",
        "    var constantHoistedExpr = Expression.Lambda(hoisted.Expression, hoisted.Environment.Select(kv => kv.Key));\n",
        "\n",
        "    if (!compiledQueries.TryGetValue(constantHoistedExpr, out var compiled))\n",
        "    {\n",
        "        Console.WriteLine($\"Compiling {constantHoistedExpr}\");\n",
        "\n",
        "        compiled = constantHoistedExpr.Compile();\n",
        "        compiledQueries.Add(constantHoistedExpr, compiled);\n",
        "    }\n",
        "\n",
        "    var constants = hoisted.Environment.Select(kv => Expression.Constant(kv.Value, kv.Key.Type)).ToArray();\n",
        "\n",
        "    var bound = Expression.Invoke(Expression.Constant(compiled, constantHoistedExpr.Type), constants);\n",
        "    object res = bound.Evaluate();\n",
        "\n",
        "    Console.WriteLine($\"Evaluating {bound} = {res}\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we can apply `Evaluate` to our query expressions which only differ in the constants used."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Compiling (@p0, @p1, @p2, @p3, @p4) => Range(@p0, @p1).Where(x => ((x % @p2) == @p3)).Select(x => (x + @p4))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Evaluating Invoke(value(System.Func`6[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Collections.Generic.IEnumerable`1[System.Int32]]), 1, 10, 2, 0, 9) = System.Linq.Enumerable+WhereSelectEnumerableIterator`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Evaluating Invoke(value(System.Func`6[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Collections.Generic.IEnumerable`1[System.Int32]]), 2, 20, 3, 1, 8) = System.Linq.Enumerable+WhereSelectEnumerableIterator`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Evaluating Invoke(value(System.Func`6[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Collections.Generic.IEnumerable`1[System.Int32]]), 3, 30, 4, 2, 7) = System.Linq.Enumerable+WhereSelectEnumerableIterator`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Evaluate(expr1);\n",
        "Evaluate(expr2);\n",
        "Evaluate(expr3);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we only compiled the query expression once and then went ahead to evaluate the compiled expression three times, with different constants."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "More advanced facilities in the `ConstantHoister` enable excluding certain constants. For example, strings passed to the format parameter of `String.Format(string, object[])` or the regular expression parameter of `Regex.Match(string, string)` tend to not vary; in fact, these are strings that encode a small embedded programming language. To exclude such constants, exclusion patterns can be added to the `ConstantHoister` constructor."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Text.RegularExpressions;\n",
        "\n",
        "var betterHoister = new ConstantHoister(useDefaultForNull: true, exclusions: new LambdaExpression[]\n",
        "{\n",
        "    (Expression<Func<string, string>>)(s => string.Format(s, default(object))),\n",
        "    (Expression<Func<string, string>>)(s => string.Format(s, default(object), default(object))),\n",
        "    (Expression<Func<string, string>>)(s => string.Format(s, default(object), default(object), default(object))),\n",
        "    (Expression<Func<string, string>>)(s => string.Format(s, default(object[]))),\n",
        "    (Expression<Func<string, Match>>)(pattern => Regex.Match(\"\", pattern)),\n",
        "});"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The patterns in the exclusion list are lambda expressions where the first parameter indicates the position where a constant node should be ignored for hoisting. For example, if the user wrote `Regex.Match(\"foobar\", \"[a-z]*\")`, then the first argument `\"foobar\"` will be hoisted as a constant, but the second argument `\"[a-z]*\"` won't be hoisted. An example is shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => Match(Format(\"{0}{1}\", @p0, @p1), \"[a-z]*\")\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<Match>> f = () => Regex.Match(string.Format(\"{0}{1}\", \"foo\", \"bar\"), \"[a-z]*\");\n",
        "\n",
        "ExpressionWithEnvironment res = betterHoister.Hoist(f);\n",
        "\n",
        "Console.WriteLine(res.Expression);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that only `\"foo\"` and `\"bar\"` are getting hoisted while the format string and regular expression constants are kept in the expression tree."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Type substitution\n",
        "\n",
        "The `TypeSubstitutionExpressionVisitor` can be used to retype an expression tree from one set of types to another set of types. This involves specifying rules to rebind members involving the types being substituted. In the context of Reaqtor, type substitution is often used to move a tree from one *type space* to another, e.g. from one set of reactive interfaces to another.\n",
        "\n",
        "A trivial example using `DateTime` and `DateTimeOffset` is shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => DateTimeOffset.Now.AddDays(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var subst = new TypeSubstitutionExpressionVisitor(new Dictionary<Type, Type>\n",
        "{\n",
        "    { typeof(DateTime), typeof(DateTimeOffset) }\n",
        "});\n",
        "\n",
        "Expression<Func<DateTime>> tomorrow = () => DateTime.Now.AddDays(1);\n",
        "\n",
        "Expression rewritten = subst.Apply(tomorrow);\n",
        "\n",
        "Console.WriteLine(rewritten);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "More advanced use cases can be supported by deriving from `TypeSubstitutionExpressionVisitor` to override various `Resolve` methods that are used to resolve reflection objects as any of the types changes. In the sample above, the substitution of `DateTime` to `DateTimeOffset` triggers lookup for `Now` and `AddDays` on `DateTimeOffset`, which can be found successfully. In some cases, more complex mappings are required. An example of a failing rewrite is shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.InvalidOperationException: No suitable constructor on declaring type 'System.DateTimeOffset' with parameter types (System.Int32, System.Int32, System.Int32) found.\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.FailResolveConstructor(ConstructorInfo originalConstructor, Type declaringType, Type[] parameters) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 434\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.ResolveConstructor(ConstructorInfo originalConstructor, Type declaringType, Type[] parameters) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 416\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.VisitConstructor(ConstructorInfo constructor) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 164\r\n   at System.Linq.CompilerServices.ExpressionVisitorWithReflection.VisitNew(NewExpression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Visitors\\ExpressionVisitorWithReflection.cs:line 965\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 643\r\n   at System.Linq.CompilerServices.ExpressionVisitorWithReflection.VisitLambdaCore[T](Expression`1 node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Visitors\\ExpressionVisitorWithReflection.cs:line 615\r\n   at System.Linq.CompilerServices.ScopedExpressionVisitorBase.VisitLambda[T](Expression`1 node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Visitors\\ScopedExpressionVisitorBase.cs:line 166\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 643\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.Apply(Expression expression) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 105\r\n   at Submission#70.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<DateTime>> birthday = () => new DateTime(1983, 2, 11);\n",
        "\n",
        "subst.Apply(birthday);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This fails because `DateTimeOffset` does not define a constructor that's isomporhic to the constructor on `DateTime`. To support this type of rewrite, we can override `VisitNew` to handle the case manually. Because `TypeSubstitutionExpressionVisitor` is just a specialized visitor, we can override any of the `Visit` methods if we have to. In this case, that's our only hope because we can't use `ResolveConstructor` to find a `ConstructorInfo` on `DateTimeOffset` that takes three `int` parameters."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class DateTimeSubstitutor : TypeSubstitutionExpressionVisitor\n",
        "{\n",
        "    private static readonly Dictionary<Type, Type> s_map = new Dictionary<Type, Type>\n",
        "    {\n",
        "        { typeof(DateTime), typeof(DateTimeOffset) }\n",
        "    };\n",
        "\n",
        "    private static readonly ConstructorInfo s_ctorDateTime_IntIntInt = typeof(DateTime).GetConstructor(new[] { typeof(int), typeof(int), typeof(int) });\n",
        "    private static readonly ConstructorInfo s_ctorDateTimeOffset_DateTime = typeof(DateTimeOffset).GetConstructor(new[] { typeof(DateTime) });\n",
        "\n",
        "    public DateTimeSubstitutor()\n",
        "        : base(s_map)\n",
        "    {\n",
        "    }\n",
        "\n",
        "    protected override Expression VisitNew(NewExpression node)\n",
        "    {\n",
        "        if (node.Constructor?.DeclaringType == typeof(DateTime))\n",
        "        {\n",
        "            if (node.Constructor == s_ctorDateTime_IntIntInt)\n",
        "            {\n",
        "                var args = Visit(node.Arguments);\n",
        "\n",
        "                return Expression.New(s_ctorDateTimeOffset_DateTime, node.Update(args));\n",
        "            }\n",
        "        }\n",
        "\n",
        "        return base.VisitNew(node);\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now, we can perform the rewrite."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => new DateTimeOffset(new DateTime(1983, 2, 11))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var betterSubst = new DateTimeSubstitutor();\n",
        "\n",
        "Console.WriteLine(betterSubst.Apply(birthday));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Furthermore, if an expression tree contains a `ConstantExpression` of a type that has to be changed, a call to a `ConvertConstant` virtual method is made, which enables for the insertion of custom conversion logic."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.InvalidOperationException: No suitable conversion of constant '02/28/2021 11:14:43' to type 'System.DateTimeOffset' found.\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.ConvertConstant(Object originalValue, Type newType) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 384\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.MakeConstant(Object value, Type type) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 673\r\n   at System.Linq.CompilerServices.ExpressionVisitorWithReflection.VisitConstant(ConstantExpression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Visitors\\ExpressionVisitorWithReflection.cs:line 263\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 643\r\n   at System.Linq.CompilerServices.TypeSubstitutionExpressionVisitor.Apply(Expression expression) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Rewriters\\TypeSystem\\TypeSubstitutionExpressionVisitor.cs:line 105\r\n   at Submission#73.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var now = Expression.Constant(DateTime.Now);\n",
        "\n",
        "Console.WriteLine(betterSubst.Apply(now));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To support this case, let's derive from our previous attempt (to reduce code in this notebook), and override `ConvertConstant` as well."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class EvenBetterDateTimeSubstitutor : DateTimeSubstitutor\n",
        "{\n",
        "    protected override object ConvertConstant(object originalValue, Type newType)\n",
        "    {\n",
        "        if (newType == typeof(DateTimeOffset) && originalValue?.GetType() == typeof(DateTime))\n",
        "        {\n",
        "            return Expression.Convert(Expression.Constant(originalValue, typeof(DateTime)), newType).Evaluate();\n",
        "        }\n",
        "\n",
        "        return base.ConvertConstant(originalValue, newType);\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, we should be able to also convert a `ConstantExpression` from `DateTime` to `DateTimeOffset`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "2/28/2021 11:14:43 AM -08:00\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var evenBetterSubst = new EvenBetterDateTimeSubstitutor();\n",
        "\n",
        "Console.WriteLine(evenBetterSubst.Apply(now));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Tupletization\n",
        "\n",
        "One of the drawbacks of delegate types in .NET is the lack of support for variadic generics, causing us to end up with a whole ladder of types to support functions with different numbers of parameters (cf. `Action<...>` and `Func<...>` families).\n",
        "\n",
        "While expression trees support the creation of `LambdaExpression` nodes with any number of parameters, it relies on runtime code generation (using `System.Reflection.Emit`) to manufacture delegate types of arities that exceed the available `Func<>` and `Action<>` types. This results in types that are tricky to carry along across machine boundaries (though Bonsai supports ways to represent function types as first-class citizens).\n",
        "\n",
        "> **Note:** One can argue that functions with more than 16 parameters should be avoided, but keep in mind that expressions are often machine generated. For example, when performing constant hoisting, the number of parameters generated is linear in the number of constants that occurred in an expression.\n",
        "\n",
        "Let's first have a look at the runtime generation of delegate types by the `Lambda` factory."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Action\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`1[System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`3[System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`4[System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`5[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`6[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`7[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`8[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`9[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`10[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`11[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`12[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`13[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`14[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`15[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Action`16[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate18$1\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate19$2\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate20$3\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`1[System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`3[System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`4[System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`5[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`6[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`7[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`8[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`9[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`10[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`11[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`12[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`13[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`14[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`15[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`16[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.Func`17[System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate18$4\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate19$5\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Delegate20$6\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "for (int i = 0; i < 20; i++)\n",
        "{\n",
        "    Console.WriteLine(Expression.Lambda(Expression.Empty(), Enumerable.Range(1, i).Select(j => Expression.Parameter(typeof(int)))).Type);\n",
        "}\n",
        "\n",
        "for (int i = 0; i < 20; i++)\n",
        "{\n",
        "    Console.WriteLine(Expression.Lambda(Expression.Constant(42), Enumerable.Range(1, i).Select(j => Expression.Parameter(typeof(int)))).Type);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This library provides a mechanism to normalize lambda expressions to unary functions using a technique called tupletization. Let's first construct a couple of sample expression trees below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var xs = Enumerable.Range(1, 20).Select(i => Expression.Parameter(typeof(int), \"x\" + i)).ToArray();\n",
        "var sum = xs.Cast<Expression>().Aggregate((l, r) => Expression.Add(l, r));\n",
        "\n",
        "Expression<Func<int>> f1 = () => 42;\n",
        "Expression<Func<int, int>> f2 = x => x + 1;\n",
        "Expression<Func<int, int, int>> f3 = (x, y) => x * y;\n",
        "LambdaExpression f20 = Expression.Lambda(sum, xs);\n",
        "\n",
        "Expression<Action> a1 = () => Console.WriteLine(42);\n",
        "Expression<Action<int>> a2 = x => Console.WriteLine(x + 1);\n",
        "Expression<Action<int, int>> a3 = (x, y) => Console.WriteLine(x * y);\n",
        "LambdaExpression a20 = Expression.Lambda(Expression.Call(typeof(Console).GetMethod(nameof(Console.WriteLine), new[] { typeof(int) }), sum), xs);\n",
        "\n",
        "var exprs = new LambdaExpression[]\n",
        "{\n",
        "    f1,\n",
        "    f2,\n",
        "    f3,\n",
        "    f20,\n",
        "    a1,\n",
        "    a2,\n",
        "    a3,\n",
        "    a20\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Using the `ExpressionTupletizer` we can convert back and forth between the N-ary function form and a so-called tupletized form, using `Pack` and `Unpack` methods. We'll illustrate this roundtripping in the next cell."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => 42\r\n  Pack:   _ => 42\r\n  Unpack: () => 42\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "x => (x + 1)\r\n  Pack:   t => (t.Item1 + 1)\r\n  Unpack: p0 => (p0 + 1)\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(x, y) => (x * y)\r\n  Pack:   t => (t.Item1 * t.Item2)\r\n  Unpack: (p0, p1) => (p0 * p1)\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20) => (((((((((((((((((((x1 + x2) + x3) + x4) + x5) + x6) + x7) + x8) + x9) + x10) + x11) + x12) + x13) + x14) + x15) + x16) + x17) + x18) + x19) + x20)\r\n  Pack:   t => (((((((((((((((((((t.Item1 + t.Item2) + t.Item3) + t.Item4) + t.Item5) + t.Item6) + t.Item7) + t.Rest.Item1) + t.Rest.Item2) + t.Rest.Item3) + t.Rest.Item4) + t.Rest.Item5) + t.Rest.Item6) + t.Rest.Item7) + t.Rest.Rest.Item1) + t.Rest.Rest.Item2) + t.Rest.Rest.Item3) + t.Rest.Rest.Item4) + t.Rest.Rest.Item5) + t.Rest.Rest.Item6)\r\n  Unpack: (p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19) => (((((((((((((((((((p0 + p1) + p2) + p3) + p4) + p5) + p6) + p7) + p8) + p9) + p10) + p11) + p12) + p13) + p14) + p15) + p16) + p17) + p18) + p19)\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "() => WriteLine(42)\r\n  Pack:   _ => WriteLine(42)\r\n  Unpack: () => WriteLine(42)\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "x => WriteLine((x + 1))\r\n  Pack:   t => WriteLine((t.Item1 + 1))\r\n  Unpack: p0 => WriteLine((p0 + 1))\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(x, y) => WriteLine((x * y))\r\n  Pack:   t => WriteLine((t.Item1 * t.Item2))\r\n  Unpack: (p0, p1) => WriteLine((p0 * p1))\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20) => WriteLine((((((((((((((((((((x1 + x2) + x3) + x4) + x5) + x6) + x7) + x8) + x9) + x10) + x11) + x12) + x13) + x14) + x15) + x16) + x17) + x18) + x19) + x20))\r\n  Pack:   t => WriteLine((((((((((((((((((((t.Item1 + t.Item2) + t.Item3) + t.Item4) + t.Item5) + t.Item6) + t.Item7) + t.Rest.Item1) + t.Rest.Item2) + t.Rest.Item3) + t.Rest.Item4) + t.Rest.Item5) + t.Rest.Item6) + t.Rest.Item7) + t.Rest.Rest.Item1) + t.Rest.Rest.Item2) + t.Rest.Rest.Item3) + t.Rest.Rest.Item4) + t.Rest.Rest.Item5) + t.Rest.Rest.Item6))\r\n  Unpack: (p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19) => WriteLine((((((((((((((((((((p0 + p1) + p2) + p3) + p4) + p5) + p6) + p7) + p8) + p9) + p10) + p11) + p12) + p13) + p14) + p15) + p16) + p17) + p18) + p19))\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "foreach (var expr in exprs)\n",
        "{\n",
        "    var sb = new StringBuilder();\n",
        "    sb.AppendLine(expr.ToString());\n",
        "\n",
        "    LambdaExpression packed = ExpressionTupletizer.Pack(expr, voidType: typeof(ValueTuple));\n",
        "    sb.AppendLine(\"  Pack:   \" + packed.ToString());\n",
        "    \n",
        "    LambdaExpression unpacked = ExpressionTupletizer.Unpack(packed, voidType: typeof(ValueTuple));\n",
        "    sb.AppendLine(\"  Unpack: \" + unpacked.ToString());\n",
        "\n",
        "    Console.WriteLine(sb);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In here, the use of `voidType` is necessary to specify how a lambda expression without any parameters is turned into a unary lambda expression with one parameter. To do so, the introduced dummy parameter needs to have a type, which is represented using `voidType`. The use of `ValueTuple` is well-suited for this purpose.\n",
        "\n",
        "Reaqtor uses the tupletized form in quite a few places to standardize on unary functions at the base layers of the platform. Any function arity is supported at layers higher up, which are merely syntactic sugar to construct expressions in tuple form."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `AnonynmousTypeTupletizer`\n",
        "\n",
        "Another rewriting utility that relies on tuples is `AnonynmousTypeTupletizer`. This expression rewriter is a type substitution visitor that replaces anonymous types (e.g. produced by `let` clauses in query expression, due to the use of transparent identifiers) by tuple types. This can be useful to shake off compiler-generated types prior to carrying out further rewrite steps (or prior to serialization of the expression for shipment to another machine). For example:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Int32[].Select(x => new <>f__AnonymousType0#51`2(x = x, y = (x + 1))).Select(t => (t.x + t.y))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var query = from x in new[] { 1, 2, 3 }.AsQueryable()\n",
        "            let y = x + 1\n",
        "            select x + y;\n",
        "\n",
        "var queryExpr = CompilerGeneratedNameEliminator.Prettify(query.Expression);\n",
        "\n",
        "Console.WriteLine(queryExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Rather than allocating anonymous types for the transparent identifiers, we can replace these by tuple types instead. This is achieved through `AnonymousTypeTupletizer.Tupletize`, which takes up to three parameters. Besides the expression to rewrite, the `unitValue` specifies the expression to use when replacing `new {}` anonymous types (due to the lack of a non-generic `Tuple` type in the BCL), and `excludeVisibleTypes` prevents the tuple rewriting from changing the type of the top-level expression. We'll get to this detail in a bit, but let's first apply the rewrite to our query expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Int32[].Select(x => new Tuple`2(x, (x + 1))).Select(t => (t.Item1 + t.Item2))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var tupletizedQueryExpr = AnonymousTypeTupletizer.Tupletize(queryExpr, unitValue: Expression.Constant(new object()), excludeVisibleTypes: true);\n",
        "\n",
        "Console.WriteLine(tupletizedQueryExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In the resulting expression, we have no anonymous types left. This simplifies the expression by reducing the number of types it relies on. This in turn makes tasks like expression serialization easier."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### CPS transformations\n",
        "\n",
        "This library provides very rudimentary support for continuation passing style (CPS) transforms of code which can be used in the context of binding query execution plans to asynchronous infrastructure.\n",
        "\n",
        "**Note:** The CPS transform support in this library only works for expressions because it originates from a LINQ provider toolkit we wrote in the .NET 3.5 days, prior to support for statement nodes. A full-blown CPS transformation framework existed in the context of Volta's tier splitting work, but it was written in CCI (the Common Compiler Infrastructure) and never got ported to .NET 4.0's expressions. While Nuqleon doesn't use this implementation of CPS transform directly (anymore), we're keeping it around for other uses (e.g. execution plans in some internal stores). A more complete CPS transformation framework could be built, especially in conjunction with the work on modernized expression trees with support for async lambdas and `await` expressions.\n",
        "\n",
        "CPS transforms involve rewriting method invocations such as `Add(a, b)` to `Add(a, b, ret => ...)` where the result is provided through a callback rather than a returned result. This then enables the use of asynchronous functions.\n",
        "\n",
        "> **Note:** This functionality has been used for execution plans in stores that have asynchronous callback-based `Get`, `Read`, `Enumerate`, etc. operations, but the user's code uses synchronous operations instead. By enabling rewrites to synchronous stub methods (e.g. `T Get<T>(string key)`) and annotating these stubs with a `UseAsyncMethod` attribute, the CPS transformation framework performs a set of tree rewrites that replace the stub method calls with their async counterparts (e.g. `void Get<T>(string key, Action<T>)`)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To illustrate this facility, let's first build the most trivial CPS transformation demo with a static `Add` method."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static class Calculator\n",
        "{\n",
        "    [UseAsyncMethod]\n",
        "    public static int Add(int x, int y) => throw new NotImplementedException();\n",
        "\n",
        "    public static void Add(int x, int y, Action<int> ret) => ret(x + y);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Given this definition, a user can write an expression of the form `Add(1, Add(2, 3))` but not that the method does not have an implementation. Instead, we want to translate the user's code to a corresponding asynchronous implementation, which is indicated by the `[UseAsyncMethod]` annotation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => Add(1, Add(2, 3))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int>> calcExpr = () => Calculator.Add(1, Calculator.Add(2, 3));\n",
        "\n",
        "Console.WriteLine(calcExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "If the underlying evaluation infrastructure happens to be asynchronous, we can use the CPS rewriter to retarget the call to `int Add(int, int)` to `void Add(int, int, Action<int>)` which is the calback-based equivalent operation. In the code below, we perform this rewrite and specify the continuation we want to invoke upon obtaining the result of evaluating the expression asynchronously."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Add(2, 3, x0 => Add(1, x0, ret => WriteLine(ret)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var rewriter = new ClassicCpsRewriter();\n",
        "\n",
        "Expression<Action<int>> continuation = ret => Console.WriteLine(ret);\n",
        "\n",
        "Expression asyncExpr = rewriter.Rewrite(calcExpr, continuation);\n",
        "\n",
        "Console.WriteLine(asyncExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can also evaluate the resulting expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "6\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression.Lambda<Action>(asyncExpr).Compile()();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A more realistic example of using the CPS transformation is to map an execution plan onto asynchronous implementations of primitive operations, e.g. in the context of a database product. Note that the CPS utilities in this library predate the introduction of `async` and `await`, but it is possible to combine these facilities with `Task<T>` based APIs. An example is shown below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static class AsyncCalculator\n",
        "{\n",
        "    [UseAsyncMethod]\n",
        "    public static int Add(int x, int y) => throw new NotImplementedException();\n",
        "\n",
        "    public static async void Add(int x, int y, Action<int> ret)\n",
        "    {\n",
        "        await Task.Delay(1000);\n",
        "        ret(x + y);\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Once more, we create a sample expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => Add(1, Add(2, 3))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int>> calcExpr = () => AsyncCalculator.Add(1, AsyncCalculator.Add(2, 3));\n",
        "\n",
        "Console.WriteLine(calcExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In order to make the entire CPS-transformed expression return a `Task<int>`, we need to make the final continuation use a `TaskCompletionSource<int>`. To do so, we can build an expression tree that's very similar to the machinery of `async` methods in C# 5.0 and beyond. First, we'll craft some variables for `TaskCompletionSource<int>` and an expression for the `Action<int>` continuation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "res => tcs.SetResult(res)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var tcs = Expression.Parameter(typeof(TaskCompletionSource<int>), \"tcs\");\n",
        "\n",
        "var result = Expression.Parameter(typeof(int), \"res\");\n",
        "var setResult = Expression.Call(tcs, typeof(TaskCompletionSource<int>).GetMethod(nameof(TaskCompletionSource<int>.SetResult), new[] { typeof(int) }), result);\n",
        "var continuation = Expression.Lambda<Action<int>>(setResult, result);\n",
        "\n",
        "Console.WriteLine(continuation);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "With a continuation expression available, we can now perform the CPS transformation on `calcExpr`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Add(2, 3, x0 => Add(1, x0, res => tcs.SetResult(res)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var rewriter = new ClassicCpsRewriter();\n",
        "\n",
        "Expression asyncExpr = rewriter.Rewrite(calcExpr, continuation);\n",
        "\n",
        "Console.WriteLine(asyncExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, we wrap the whole fanfare into a async ramp function that instantiates the `TaskCompletionSource<int>`, stores it in a local, kicks off the async operation, and finally returns the `Task`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => {var tcs; ... }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var task = Expression.Property(tcs, typeof(TaskCompletionSource<int>).GetProperty(nameof(TaskCompletionSource<int>.Task)));\n",
        "var newTcs = Expression.New(typeof(TaskCompletionSource<int>).GetConstructor(Type.EmptyTypes));\n",
        "\n",
        "var calcAsync =\n",
        "    Expression.Lambda<Func<Task<int>>>(\n",
        "        Expression.Block(\n",
        "            new[] { tcs },\n",
        "            Expression.Assign(tcs, newTcs),\n",
        "            asyncExpr,\n",
        "            task\n",
        "        )\n",
        "    );\n",
        "\n",
        "Console.WriteLine(calcAsync);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "At long last, we can evaluate the expression and wait for the task's completion (here using `.Result` for simplicity in the notebook)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "6\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Task<int> t = calcAsync.Evaluate<Task<int>>();\n",
        "\n",
        "Console.WriteLine(t.Result); // This should take 2 seconds to complete due to the Task.Delay(1000) inside Add, which gets invoked twice."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To support propagation of errors, the `ClassicCpsRewriterWithErrorPropagation` rewriter can be used instead. Rather than rewriting synchronous methods to methods taking in a single callback of type `Action<T>`, an additional callback of type `Action<Exception>` is passed for the error continuation. We can illustrate this using a `Div` function that can throw `DivideByZeroException`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static class AsyncFancyCalculator\n",
        "{\n",
        "    [UseAsyncMethod]\n",
        "    public static int Div(int x, int y) => throw new NotImplementedException();\n",
        "\n",
        "    public static async void Div(int x, int y, Action<int> ret, Action<Exception> error)\n",
        "    {\n",
        "        await Task.Delay(1000);\n",
        "        if (y == 0)\n",
        "        {\n",
        "            error(new DivideByZeroException());\n",
        "        }\n",
        "        else\n",
        "        {\n",
        "            ret(x / y);\n",
        "        }\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We'll repeat all of the steps carried out earlier, but this time using a `ClassicCpsRewriterWithErrorPropagation` instead."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static Expression<Func<Task<int>>> MakeAsync(Expression<Func<int>> expr)\n",
        "{\n",
        "    // TaskCompletionSource<int> tcs\n",
        "    var tcs = Expression.Parameter(typeof(TaskCompletionSource<int>), \"tcs\");\n",
        "\n",
        "    // int res\n",
        "    var result = Expression.Parameter(typeof(int), \"res\");\n",
        "\n",
        "    // Exception ex\n",
        "    var exception = Expression.Parameter(typeof(Exception), \"ex\");\n",
        "\n",
        "    // tcs.SetResult(res)\n",
        "    var setResult = Expression.Call(tcs, typeof(TaskCompletionSource<int>).GetMethod(nameof(TaskCompletionSource<int>.SetResult), new[] { typeof(int) }), result);\n",
        "\n",
        "    // tcs.SetException(ex)\n",
        "    var setException = Expression.Call(tcs, typeof(TaskCompletionSource<int>).GetMethod(nameof(TaskCompletionSource<int>.SetException), new[] { typeof(Exception) }), exception);\n",
        "\n",
        "    // (int res) => tcs.SetResult(res)\n",
        "    var onSuccess = Expression.Lambda<Action<int>>(setResult, result);\n",
        "\n",
        "    // (Exception ex) => tcs.SetException(ex)\n",
        "    var onError = Expression.Lambda<Action<Exception>>(setException, exception);\n",
        "\n",
        "    // Op(arg_1, ..., arg_n, (int res) => tcs.SetResult(res), (Exception ex) => tcs.SetException(ex))\n",
        "    var asyncExpr = new ClassicCpsRewriterWithErrorPropagation().Rewrite(expr, onSuccess, onError);\n",
        "\n",
        "    // new TaskCompletionSource<int>()\n",
        "    var newTcs = Expression.New(typeof(TaskCompletionSource<int>).GetConstructor(Type.EmptyTypes));\n",
        "\n",
        "    // tcs.Task\n",
        "    var task = Expression.Property(tcs, typeof(TaskCompletionSource<int>).GetProperty(nameof(TaskCompletionSource<int>.Task)));\n",
        "\n",
        "    // new Func<Task<int>>(() =>\n",
        "    // {\n",
        "    //     var tcs = new TaskCompletionSource<int>();\n",
        "    //     Op(arg_1, ..., arg_n, (int res) => tcs.SetResult(res), (Exception ex) => tcs.SetException(ex))\n",
        "    //     return tcs.Task;\n",
        "    // })\n",
        "    var calcAsync =\n",
        "        Expression.Lambda<Func<Task<int>>>(\n",
        "            Expression.Block(\n",
        "                new[] { tcs },\n",
        "                Expression.Assign(tcs, newTcs),\n",
        "                asyncExpr,\n",
        "                task\n",
        "            )\n",
        "        );\n",
        "\n",
        "    return calcAsync;\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's now run this for two different expressions and observe the result or error getting propagated through the `Task<int>` object."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "1\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.DivideByZeroException: Attempted to divide by zero.\r\n   at Submission#93.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Task<int> resSuccess = MakeAsync(() => AsyncFancyCalculator.Div(3, 2)).Compile()();\n",
        "Task<int> resError = MakeAsync(() => AsyncFancyCalculator.Div(1, 0)).Compile()();\n",
        "\n",
        "Console.WriteLine(await resSuccess);\n",
        "Console.WriteLine(await resError); // Will throw!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Expression tree evaluation\n",
        "\n",
        "Evaluation of expression trees can be done using `Compile` methods on `LambdaExpression` and `Expression<TDelegate>` as shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "42\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int>> f = () => 42;\n",
        "\n",
        "Func<int> d = f.Compile();\n",
        "\n",
        "int x = d();\n",
        "\n",
        "Console.WriteLine(x);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "By default, `Compile` will use `System.Reflection.Emit` to generate IL code at runtime. There's also support for using an interpreter using a Boolean `preferInterpretation` flag, which can be faster if the expression is simple. Furthermore, it can reduce costs (due to IL code generation and JIT compilation) if the expression is only to be evaluated once. If the expression is evaluated often or is rather complex, compiled expressions tend to perform better."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "42\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Func<int> d = f.Compile(preferInterpretation: true);\n",
        "\n",
        "int x = d();\n",
        "\n",
        "Console.WriteLine(x);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "All of the above are part of the `System.Linq.Expressions` library in the BCL. This library adds some functionality on top of this."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### The `Evaluate` and `Funcletize` extension methods\n",
        "\n",
        "First of all, this library provides a number of methods that make it easier to perform evaluation of any `Expression` without having to manually construct a `LambdaExpression` or `Expression<TDelegate>` around it. This wrapping step is simplified using `Funcletize`, as shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "() => 42\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression expr = Expression.Constant(42);\n",
        "\n",
        "Expression<Func<int>> eval = expr.Funcletize<int>();\n",
        "\n",
        "Console.WriteLine(eval);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This can then be used to call `Compile()` in order to perform evaluation. However, if the end goal is to just do that, we can directly call `Evaluate` instead, as shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "42\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "int answer = expr.Evaluate<int>();\n",
        "\n",
        "Console.WriteLine(answer);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Where things become more interesting is in the additional `ICompiledDelegateCache` that can be passed to `Evaluate` overloads."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Using compiled delegate caches with `ICompiledDelegateCache`\n",
        "\n",
        "Compiled delegate caches use expression tree equality comparison to avoid reocmpiling expression trees that have been compiled previously. We demonstrated this technique earlier in this notebook by building a `Dictionary<LambdaExpression, Delegate>`, when discussing constant hoisting. The built-in support for `ICompiledDelegateCache` makes this task easier, while also providing for caching policies. To illustrate the effect of compiled delegate caching, we'll first define a little benchmark utility."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Time;\n",
        "\n",
        "class MemoryClock : IClock\n",
        "{\n",
        "    public long Now => GC.GetAllocatedBytesForCurrentThread();\n",
        "}\n",
        "\n",
        "IStopwatch swMem = StopwatchFactory.FromClock(new MemoryClock()).Create();\n",
        "IStopwatch swTime = StopwatchFactory.Diagnostics.Create();\n",
        "\n",
        "void Benchmark(string title, Action test, int n)\n",
        "{\n",
        "    swMem.Restart();\n",
        "    swTime.Restart();\n",
        "\n",
        "    for (int i = 0; i < n; i++)\n",
        "    {\n",
        "        test();\n",
        "    }\n",
        "\n",
        "    swTime.Stop();\n",
        "    swMem.Stop();\n",
        "\n",
        "    Console.WriteLine($\"{title} completed in {swTime.ElapsedMilliseconds} ms and allocated {swMem.ElapsedTicks} bytes.\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, we'll craft a little expression tree to test compilation with. Note we won't evaluate this expression; instead, we'll use `ICompiledDelegateCache` as a parameter to a `Compile` extension method defined in this library. Our goal is to compare the cost of always calling `Compile()` versus calling `Compile(ICompiledDelegateCache)`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "Expression<Func<string, int>> expr = s => s.ToUpper().Substring(1, 2).ToLower().Length - 1;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To test compiled delegate caches, we'll start off with a `SimpleCompiledDelegateCache` which has an unbounded cache size. Alternatively we could use the `LeastRecentlyUsedCompiledDelegateCache` which has an LRU cache eviction policy."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Without caching completed in 1677 ms and allocated 49214568 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "With caching completed in 246 ms and allocated 47700904 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var cache = new SimpleCompiledDelegateCache();\n",
        "\n",
        "Benchmark(\"Without caching\", () => expr.Compile(), 10_000);\n",
        "Benchmark(\"With caching\", () => expr.Compile(cache), 10_000);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The time taken to compile an expression that has been compiled before is significantly shorter because we're avoiding going into `System.Reflection.Emit` and (down the line) triggering JIT compilation. In the code below, we'll also invoke the compiled delegate."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Without caching completed in 1881 ms and allocated 49280624 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "With caching completed in 206 ms and allocated 48731968 bytes.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var cache = new SimpleCompiledDelegateCache();\n",
        "\n",
        "Benchmark(\"Without caching\", () => expr.Compile()(\"foobar\"), 10_000);\n",
        "Benchmark(\"With caching\", () => expr.Compile(cache)(\"foobar\"), 10_000);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The difference is even more pronounced when we try to compile expressions concurrently, which mimics exactly what happens during recovery of query evaluators in Reaqtor. Due to locks inside the CLR (around the code generation area), we end up with a slow down due to lock contention. It should also be noted that the total memory cost reported here is far lower than the real cost involved due to much of the memory allocations happening on the native side of the CLR. Our `MemoryClock` only accounts for managed memory allocations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Without caching completed in 470784 ms and allocated 607413072 bytes (using 12 threads).\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "With caching completed in 6037 ms and allocated 579592976 bytes (using 12 threads).\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.Threading;\n",
        "\n",
        "void BenchmarkConcurrent(string title, Action compileAndEval, int n)\n",
        "{\n",
        "    long totalMs = 0L;\n",
        "    long totalBytes = 0L;\n",
        "\n",
        "    var threads =\n",
        "        Enumerable.Range(0, Environment.ProcessorCount).Select(_ =>\n",
        "            new Thread(() =>\n",
        "            {\n",
        "                IStopwatch swMem = StopwatchFactory.FromClock(new MemoryClock()).StartNew();\n",
        "                IStopwatch swTime = StopwatchFactory.Diagnostics.StartNew();\n",
        "\n",
        "                for (int i = 0; i < n; i++)\n",
        "                {\n",
        "                    compileAndEval();\n",
        "                }\n",
        "\n",
        "                Interlocked.Add(ref totalMs, swTime.ElapsedMilliseconds);\n",
        "                Interlocked.Add(ref totalBytes, swMem.ElapsedTicks);\n",
        "            })\n",
        "        ).ToArray();\n",
        "\n",
        "    foreach (var thread in threads)\n",
        "    {\n",
        "        thread.Start();\n",
        "    }\n",
        "\n",
        "    foreach (var thread in threads)\n",
        "    {\n",
        "        thread.Join();\n",
        "    }\n",
        "\n",
        "    Console.WriteLine($\"{title} completed in {totalMs} ms and allocated {totalBytes} bytes (using {Environment.ProcessorCount} threads).\");\n",
        "}\n",
        "\n",
        "var cache = new SimpleCompiledDelegateCache();\n",
        "\n",
        "BenchmarkConcurrent(\"Without caching\", () => expr.Compile()(\"foobar\"), 10_000);\n",
        "BenchmarkConcurrent(\"With caching\", () => expr.Compile(cache)(\"foobar\"), 10_000);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that `SimpleCompiledDelegateCache` is thread-safe, so it's okay to have concurrent compilations all trying to access the cache."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Compilation using compiled delegate caching has a few more knobs that can be turned using overloads of `Compile`. The most flexible overload has the following signature:\n",
        "\n",
        "```csharp\n",
        "public static T Compile<T>(this Expression<T> expression, ICompiledDelegateCache cache, bool outliningEnabled, IConstantHoister hoister);\n",
        "```\n",
        "\n",
        "Outlining (as the opposite of inlining) can be used when expressions have nested lambdas. For example, `xs => xs.Where(x => x > 0).Select(x => x * 2)` has inner lambdas `x => x > 0` and `x => x * 2`. By using outlining, we'll compile this inner lambda using caching as well, allowing for reuse if an identical lambda occurs elsewhere. For example, if another expression has `ys => ys.Select(y => y + 1).Where(y => y > 4)`, we can reuse a cached compiled lambda of the form `t => t > c` where `c` is a hoisted constant. Both `x => x > 0` and `y => y > 4` match this pattern, for different constants.\n",
        "\n",
        "A custom hoister can also be specified, for example to add exclusion rules (e.g. for the format string in `string.Format(string, object[])`) as described earlier in this notebook.\n",
        "\n",
        "We'll finish our discussion of compiled delegate caching by illustrating the use of outlining (which is enabled by default when using simpler overloads of `Compile`)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "Expression<Func<IEnumerable<int>, IEnumerable<int>>> queryExpr1 = xs => xs.Where(x => x > 0).Take(1);\n",
        "Expression<Func<IEnumerable<int>, IEnumerable<int>>> queryExpr2 = ys => ys.Take(2).Where(y => y > 3);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Both expressions have a nested lambda of the form `t => t > c` for some constant value `c`. When outlining is enabled, we'll end up hoisting these inner lambdas out of the original expression, and will compile (and cache) them separately. We can visualize this by making use of events declared on `LeastRecentlyUsedCompiledDelegateCache` which can be used to inspect additions, hits, and removals of entries in the cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var cache = new LeastRecentlyUsedCompiledDelegateCache(capacity: 16);\n",
        "\n",
        "cache.Added += (object o, CacheEventArgs args) =>\n",
        "{\n",
        "    Console.WriteLine($\"Added {args.Lambda} to cache.  Delegate = {args.Delegate.GetHashCode()}\");\n",
        "};\n",
        "\n",
        "cache.Hit += (object o, CacheEventArgs args) =>\n",
        "{\n",
        "    Console.WriteLine($\"Retrieved {args.Lambda} from cache. Delegate = {args.Delegate.GetHashCode()}\");\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we can try to compile the first query expression using the cache, with outlining enabled (which is the default behavior for the simpler `Compile` overload used below)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Added t => x => (x > t.Item1) to cache.  Delegate = 1753183328\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Added t => xs => xs.Where(t.Item1).Take(t.Item2) to cache.  Delegate = 153197105\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "queryExpr1.Compile(cache);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that two delegates were added to the cache. One for the inner lambda and one for the outer lambda. If we try to compile the same query expression again, we should see two hits."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Retrieved t => x => (x > t.Item1) from cache. Delegate = 1753183328\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Retrieved t => xs => xs.Where(t.Item1).Take(t.Item2) from cache. Delegate = 153197105\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "queryExpr1.Compile(cache);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's finally try to compile the second expression, where the inner lambda is identical modulo parameter names and constant values. We should see a hit for this lambda, but not for the outer lambda which has a different structure than the first expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Retrieved t => y => (y > t.Item1) from cache. Delegate = 1753183328\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Added t => ys => ys.Take(t.Item1).Where(t.Item2) to cache.  Delegate = 896984621\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "queryExpr2.Compile(cache);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Expression tree optimization\n",
        "\n",
        "This library provides a few expression tree optimizations. More optimizations are available in `Nuqleon.Linq.Expressions.Optimizers`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Delegate invocation inlining\n",
        "\n",
        "The `DelegateInvocationInliner` provides a very narrow optimization that looks for `InvocationExpression` nodes whose target is a `ConstantExpression` containing a delegate-typed expression. If the delegate has an invocation list with a single invocation target (i.e. it's not a multicast delegate with multiple invocation targets attached to it), the tree is rewritten to a `MethodCallExpression` for the method targeted by the delegate.\n",
        "\n",
        "This optimization can be useful after carrying out binding steps where the binding targets for functions are `ConstantExpression`s containing delegates pointing at a function's implementation."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "As an example, consider an unbound expression `abs(1)`, as crafted below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "abs(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var abs = Expression.Parameter(typeof(Func<int, int>), \"abs\");\n",
        "var expr = Expression.Invoke(abs, Expression.Constant(1));\n",
        "\n",
        "Console.WriteLine(expr.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we're using `ToCSharpString` which prints the expression tree in a C#-like syntax. We'll discuss this later in the notebook.\n",
        "\n",
        "Given this unbound expression, we can perform binding steps as we've illustrated before in the context of beta reduction. First, we'll find all of the unbound variables using the `FreeVariableScanner`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "abs : Func<int, int>\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var variables = FreeVariableScanner.Scan(expr).ToArray();\n",
        "\n",
        "foreach (var variable in variables)\n",
        "{\n",
        "    Console.WriteLine($\"{variable.Name} : {variable.Type.ToCSharpString()}\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we're using `ToCSharpString` on an instance of type `Type` to print the type using C#-like syntax. We'll discuss this later in the notebook.\n",
        "\n",
        "Just like we've done before while discussing beta reduction, we'll go ahead and perform lambda lifting to declare all of the unbound variables in a surrounding lambda expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(Func<int, int> abs) => abs(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var lifted = Expression.Lambda(expr, variables);\n",
        "\n",
        "Console.WriteLine(lifted.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "As the next step to achieve expression binding, we'll introduce a registry of expressions to bind. This is similar to what we've done for beta reduction, but we'll make a sight change this time around."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var registry = new Dictionary<string, Expression>\n",
        "{\n",
        "    { \"abs\", Expression.Constant(new Func<int, int>(Math.Abs)) }\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The difference lies in the expression used to bind `abs`. Rather than using an `Expression<Func<int, int>>` of the form `x => Math.Abs(x)`, we're using a `ConstantExpression` that holds a delegate to `Math.Abs`.\n",
        "\n",
        "Given this registry, we can bind the functions and construct an `InvocationExpression` around the `LambdaExpression` we built earlier."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((Func<Func<int, int>, int>)((Func<int, int> abs) => abs(1)))(__c0)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var bindings = variables.Select(variable => registry[variable.Name]).ToArray();\n",
        "\n",
        "var bound = Expression.Invoke(lifted, bindings);\n",
        "\n",
        "Console.WriteLine(bound.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note the presence of `__c0` in the textual output, which represents an opaque `ConstantExpression` which could not be printed in C# syntax. This is our delegate to `Math.Abs`. Using `ToCSharp` rather than `ToCSharpExpression`, we can inspect this as well."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Global variables: {  }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Code: ((Func<Func<int, int>, int>)((Func<int, int> abs) => abs(1)))(__c0)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Constants: __c0 : System.Func`2[System.Int32,System.Int32]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "CSharpExpression cs = bound.ToCSharp();\n",
        "\n",
        "Console.WriteLine($\"Global variables: {{ {string.Join(\", \", cs.GlobalVariables)} }}\");\n",
        "Console.WriteLine($\"Code: {cs.Code}\");\n",
        "Console.WriteLine($\"Constants: {string.Join(\", \", cs.Constants.Select(kv => $\"{kv.Key} : {kv.Value.Value.ToString()}\"))}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To simplify the bound expression, we can apply beta reduction."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "__c0(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var simplified = BetaReducer.Reduce(bound);\n",
        "\n",
        "Console.WriteLine(simplified.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The result is an `InvocationExpression` that will invoke the delegate stored in the `ConstantExpression`. This does have some overhead (due to extracting the constant and invoking the delegate) which can be reduced by using `DelegateInvocationInliner` to unpack the delegate and call the underlying method directly using a `MethodCallExpression`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Math.Abs(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var result = DelegateInvocationInliner.Apply(simplified, inlineNonPublicMethods: false);\n",
        "\n",
        "Console.WriteLine(result.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Expression tree interning\n",
        "\n",
        "Because expression trees are immutable, they can be shared safely. For example, if two expressions have a common subexpression, the same object can be used to represent that common subexpression:\n",
        "\n",
        "```csharp\n",
        "f() + g() + h()\n",
        "```\n",
        "\n",
        "and\n",
        "\n",
        "```csharp\n",
        "f() + g() + i()\n",
        "```\n",
        "\n",
        "can reuse the common subexpression `f() + g()`. However, it's not always possible to figure out that two or more expressions have commonalities that present opportunities for sharing. For example, when expression visitors are used to manipulate expression trees, commonalities may not occur until rewrites have completed.\n",
        "\n",
        "As an example, let's build a few simpler expressions that have a opportunities for sharing:\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((1 * 2) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 4)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) - 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var expr1 = Expression.Add(Expression.Multiply(Expression.Constant(1), Expression.Constant(2)), Expression.Constant(3));\n",
        "var expr2 = Expression.Add(Expression.Multiply(Expression.Constant(1), Expression.Constant(2)), Expression.Constant(3));\n",
        "var expr3 = Expression.Add(Expression.Multiply(Expression.Constant(1), Expression.Constant(2)), Expression.Constant(4));\n",
        "var expr4 = Expression.Subtract(Expression.Multiply(Expression.Constant(1), Expression.Constant(2)), Expression.Constant(3));\n",
        "\n",
        "Console.WriteLine(expr1);\n",
        "Console.WriteLine(expr2);\n",
        "Console.WriteLine(expr3);\n",
        "Console.WriteLine(expr4);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Expression tree interning allows for the detection of common subexpressions across a \"forest\" of trees, and rewrite expressions to allow for reuse of common subexpressions, thus reducing the memory utilitization. This is very similar to `string.Intern`, although the latter only operates on complete strings, while expression tree interning can consider every subexpression.\n",
        "\n",
        "> **Note:** Interning is quite expensive due to the computations involved to figure out commonalities between expressions. It's only recommended to use interning if expressions are long-lived. In the context of Nuqleon, this is most useful when expression trees are kept alive in registries or on quotations that are needed to support higher-order query operators (e.g. in `xs.SelectMany(x => f(x))`, the expression `x => f(x)` is kept - even after compilation to a delegate - because inner subscriptions need to be able to construct an expression, which will get checkpointed, that represents the observable `f(x)` for a given value of `x`)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's try applying interning to the expressions shown above."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((1 * 2) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 4)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) - 3)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var cache = new ExpressionInterningCache();\n",
        "\n",
        "var expr1_i = expr1.Intern(cache);\n",
        "var expr2_i = expr2.Intern(cache);\n",
        "var expr3_i = expr3.Intern(cache);\n",
        "var expr4_i = expr4.Intern(cache);\n",
        "\n",
        "Console.WriteLine(expr1_i);\n",
        "Console.WriteLine(expr2_i);\n",
        "Console.WriteLine(expr3_i);\n",
        "Console.WriteLine(expr4_i);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can start by spot-checking a few equalities to check whether interning had an effect. For example, `expr1_i` and `expr2_i` should be identical, even though `expr1` and `expr2` were not."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "(expr1   == expr2  ) = False\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(expr1_i == expr2_i) = True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine($\"(expr1   == expr2  ) = {expr1   == expr2  }\");\n",
        "Console.WriteLine($\"(expr1_i == expr2_i) = {expr1_i == expr2_i}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In order to investigate interior nodes for reference equality, we can build a simple visitor that will print all nodes and their hash code."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class PrintHashCodeVisitor : ExpressionVisitor\n",
        "{\n",
        "    public override Expression Visit(Expression node)\n",
        "    {\n",
        "        if (node != null)\n",
        "        {\n",
        "            Console.WriteLine($\"{node} [{node.GetHashCode()}]\");\n",
        "        }\n",
        "\n",
        "        return base.Visit(node);\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can first run this visitor on the original expressions to see that all nodes are unique."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((1 * 2) + 3) [51702607]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [21677825]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [58579833]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [14353293]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [31461808]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 3) [6640112]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [41526577]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [43429837]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [55763179]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [65906365]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 4) [41625339]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [51034564]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [37347377]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [57175769]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "4 [40458121]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) - 3) [28267618]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [29122994]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [27878069]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [66236554]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [67049879]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var printer = new PrintHashCodeVisitor();\n",
        "\n",
        "printer.Visit(expr1);\n",
        "printer.Visit(expr2);\n",
        "printer.Visit(expr3);\n",
        "printer.Visit(expr4);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "When we run the visitor over the interned nodes, we can see the effect of deduplicating nodes that are equivalent."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "((1 * 2) + 3) [51702607]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [21677825]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [58579833]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [14353293]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [31461808]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 3) [51702607]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [21677825]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [58579833]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [14353293]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [31461808]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) + 4) [35784226]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [21677825]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [58579833]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [14353293]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "4 [40458121]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "((1 * 2) - 3) [12841208]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "(1 * 2) [21677825]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "1 [58579833]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "2 [14353293]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "3 [31461808]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "printer.Visit(expr1_i);\n",
        "printer.Visit(expr2_i);\n",
        "printer.Visit(expr3_i);\n",
        "printer.Visit(expr4_i);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Expression tree interning only considers semantic equivalence of expressions. For example, interning `x => x + 1` and `y => y + 1` can result in variable renaming because both lambda expressions are equivalent.\n",
        "\n",
        "> **Note**: If this is not desirable, one can specify a custom `ExpressionEqualityComparator` that overrides the behavior for equality of `ParameterExpression` nodes to include the `Name` property."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "x => (x + 1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "x => (x + 1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Expression<Func<int, int>> f1 = x => x + 1;\n",
        "Expression<Func<int, int>> f2 = y => y + 1;\n",
        "\n",
        "var f1_i = f1.Intern();\n",
        "var f2_i = f2.Intern();\n",
        "\n",
        "Console.WriteLine(f1_i);\n",
        "Console.WriteLine(f2_i);\n",
        "Console.WriteLine(f1_i == f2_i);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Diagnostics\n",
        "\n",
        "To assist with logging or debugging of expression trees, this library provides a `ToCSharpString` extension method for `Expression` which produces C#-like syntax to represent the tree. Not all constructs in expression trees can be (correctly) represented in C# (e.g. `LoopExpression` having a result), so the resulting syntax just looks and feels like C#.\n",
        "\n",
        "> **Note:** Better expression tree printing support is available in https://github.com/bartdesmet/ExpressionFutures/tree/master/CSharpExpressions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "1 + x\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var expr = Expression.Add(Expression.Constant(1), Expression.Parameter(typeof(int), \"x\"));\n",
        "\n",
        "Console.WriteLine(expr.ToCSharpString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "An additional Boolean parameter called `allowCompilerGeneratedNames` can be passed to `ToCSharpString` to control whether the resulting string can contain compiler-generated names (otherwise, an exception will be thrown when encountering such a name). To illustrate this, let's have th C# compiler craft a closure type (also known as a display class)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static class C\n",
        "{\n",
        "    public static Expression Expression\n",
        "    {\n",
        "        get\n",
        "        {\n",
        "            int x = 42;\n",
        "            Expression<Func<int>> f = () => x;\n",
        "            return f.Body;\n",
        "        }\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This expression will be of the form `Member(Constant(closure), FieldInfo(\"x\"))` in pseudo-code. We can now construct an expression tree whose C# syntax requires to reveal the type, e.g. a `default(T)` expression."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "default(<>c__DisplayClass1_0)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var closureType = ((MemberExpression)C.Expression).Expression.Type;\n",
        "\n",
        "var expr = Expression.Default(closureType);\n",
        "\n",
        "Console.WriteLine(expr.ToCSharpString(allowCompilerGeneratedNames: true));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Clearly this is not valid C# syntax. In fact, the whole purpose of the `<>__` naming prefix is to ensure that compiler-generated type names cannot conflict with identifiers introduced by user code, and to prevent user code from directly accessing these types. If we disable `allowCompilerGeneratedNames`, an exception is thrown instead."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.InvalidOperationException: Compiler-generated C# type encountered: Submission#32+C+<>c__DisplayClass1_0\r\n   at System.TypeExtensions.TypePrinter.Visit(Type type) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\TypeSystem\\TypeExtensions.cs:line 711\r\n   at System.TypeExtensions.ToCSharpString(Type type, Boolean useNamespaceQualifiedNames, Boolean useCSharpTypeAliases, Boolean disallowCompilerGeneratedTypes) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\TypeSystem\\TypeExtensions.cs:line 665\r\n   at System.Linq.Expressions.ExpressionCSharpPrinter.PrintType(Type type) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Diagnostics\\ExpressionCSharpPrinter.cs:line 1152\r\n   at System.Linq.Expressions.ExpressionCSharpPrinter.VisitDefault(DefaultExpression expression) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Diagnostics\\ExpressionCSharpPrinter.cs:line 904\r\n   at System.Linq.CompilerServices.ExpressionVisitor`1.Visit(Expression node) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\Visitors\\ExpressionVisitorBase.Generic.cs:line 170\r\n   at System.Linq.Expressions.ExpressionExtensions.ToCSharpStringImpl(Expression expression, Boolean allowCompilerGeneratedNames) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\ExpressionExtensions.cs:line 332\r\n   at System.Linq.Expressions.ExpressionExtensions.ToCSharpString(Expression expression, Boolean allowCompilerGeneratedNames) in D:\\Projects\\Reaqtive\\reaqtor\\Nuqleon\\Core\\LINQ\\Nuqleon.Linq.CompilerServices\\Expressions\\ExpressionExtensions.cs:line 243\r\n   at Submission#34.<<Initialize>>d__0.MoveNext()\r\n--- End of stack trace from previous location ---\r\n   at Microsoft.CodeAnalysis.Scripting.ScriptExecutionState.RunSubmissionsAsync[TResult](ImmutableArray`1 precedingExecutors, Func`2 currentExecutor, StrongBox`1 exceptionHolderOpt, Func`2 catchExceptionOpt, CancellationToken cancellationToken)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(expr.ToCSharpString(allowCompilerGeneratedNames: false));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Alternatively, the `ToCSharp` method can be used which returns a `CSharpExpression`, providing additional information about the tree, alongside a string representation. This additional information includes a table of `Constants` as well as a list of `GlobalParameters`. An example is shown below, where we have an opaque constant that doesn't have a C# representation, and an unbound variable."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "__c0 + t\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Globals:\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "  t\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Constants:\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "  [__c0, 3/4/2021 12:32:16 PM]\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var expr = Expression.Add(Expression.Constant(DateTime.Now), Expression.Parameter(typeof(TimeSpan), \"t\"));\n",
        "\n",
        "CSharpExpression csharpExpr = expr.ToCSharp();\n",
        "\n",
        "Console.WriteLine(csharpExpr.Code);\n",
        "\n",
        "Console.WriteLine(\"Globals:\");\n",
        "\n",
        "foreach (var global in csharpExpr.GlobalVariables)\n",
        "{\n",
        "    Console.WriteLine(\"  \" + global);\n",
        "}\n",
        "\n",
        "Console.WriteLine(\"Constants:\");\n",
        "\n",
        "foreach (var constant in csharpExpr.Constants)\n",
        "{\n",
        "    Console.WriteLine(\"  \" + constant);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## BURS\n",
        "\n",
        "BURS stands for Bottom-Up Rewrite System and is based on the https://www.researchgate.net/publication/220752446_Simple_and_Efficient_BURS_Table_Generation paper. It provides for a table-driven weight-based approach to generate code. The tables contain rules which consist of patterns to recognize, a cost, and a rewrite rule.\n",
        "\n",
        "This library generalizes the BURS mechanism to conversions between a generalized notion of trees, represented as `ITree<T>`. In this context, BURS is a table-driven way to build a compiler that translates between an `ITree<T>` to an `ITree<R>`. The special case of rewriting from an `ITree<T>` to an `ITree<T>` is a rule-driven optimizer."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Building a rewriter\n",
        "\n",
        "As an example, consider a first `ITree<T>` where `T` represents node information for a tree of some arithmetic language providing unary operators `+` and `-`, as well as binary operators `+`, `-`, `*`, and `%`. Building the whole `ITree<T>` implementation in the notebook gets a bit unweildy, so we'll just import a `SampleTrees` assembly that can be found in this repo, and is also used for testing."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "#r \"..\\SampleTrees\\bin\\Debug\\net5.0\\SampleTrees.dll\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can now explore these tree types and try to craft an expression in this arithmetic expression language."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Add(Mul(Add(Mul(Const(2), Const(3)), Const(1)), Mul(Const(4), Const(5))), Const(6))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using SampleTrees.Arithmetic;\n",
        "\n",
        "var arithExpr = new Add(\n",
        "    new Mul(\n",
        "        new Add(\n",
        "            new Mul(\n",
        "                new Const(2),\n",
        "                new Const(3)\n",
        "            ),\n",
        "            new Const(1)\n",
        "        ),\n",
        "        new Mul(\n",
        "            new Const(4),\n",
        "            new Const(5)\n",
        "        )\n",
        "    ),\n",
        "    new Const(6)\n",
        ");\n",
        "\n",
        "Console.WriteLine(arithExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, let's have a look at a second expression language, which we call numerical (for lack of a better name). It's similar to the arithmetic language, but has some different node types."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "TimesPlus(Inc(Times(2, 3)), Times(4, 5), 6)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using SampleTrees.Numerical;\n",
        "\n",
        "var numExpr = new TimesPlus(\n",
        "    new Inc(\n",
        "        new Times(\n",
        "            new Val(2),\n",
        "            new Val(3)\n",
        "        )\n",
        "    ),\n",
        "    new Times(\n",
        "        new Val(4),\n",
        "        new Val(5)\n",
        "    ),\n",
        "    new Val(6)\n",
        ");\n",
        "\n",
        "Console.WriteLine(numExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note how this second language has nodes like `Inc` and `TimesPlus` which are unary and ternary specialized operators. While this sample is quite academic in nature, it has resemblances to instructions in specialized hardware or highly optimized libraries for BLAS operations. Also note that the two expressions we built in the `Arithmetic` and `Numerical` languages are equivalent. Both compute the same result.\n",
        "\n",
        "With BURS, we can write a rule-driven translator that takes an expression from the `Arithmetic` language and translates it to the `Numerical` language. Each rule has weights associates with it, and the rewriter tries to find a rewrite with the lowest weight. For example, we'd like `Add(Mul(2, 3), 1)` to use the specialized `Inc` rather than `Plus` with an operand of value `1`. Similarly, we'd like an `Add(Mul(a, b), c)` where `c` is different from `1` to leverage the specialized `TimesPlus` operator.\n",
        "\n",
        "In the cell below, we'll go ahead and construct a BURS rewriter."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.IO;\n",
        "using System.Linq.CompilerServices;\n",
        "\n",
        "var logger = new StringWriter();\n",
        "\n",
        "var burw = new BottomUpRewriter<ArithExpr, ArithNodeType, NumExpr, ArithWildcardFactory>\n",
        "{\n",
        "    // Leaf nodes\n",
        "    Leaves =\n",
        "    {\n",
        "        { (Const c) => new Val(c.Value), 1 },\n",
        "    },\n",
        "\n",
        "    // Tree patterns\n",
        "    Rules =\n",
        "    {\n",
        "        { (l, r) => new Add(l, r), (l, r) => new Plus(l, r), 2 },\n",
        "        { (l, r) => new Mul(l, r), (l, r) => new Times(l, r), 3 },\n",
        "        { (a, b, c) => new Add(new Mul(a, b), c), (a, b, c) => new TimesPlus(a, b, c), 4 },\n",
        "        { x => new Add(x, new Const(1)), x => new Inc(x), 1 },\n",
        "    },\n",
        "\n",
        "    Log = logger\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The most interesting bit is the rules table which maps patterns on the left in the source language to productions on the right in the target language, with an associated weight. The leaf nodes collection tells the rewriter how to take nullary leaf nodes from the source to the target language. We also hooked up a logger to see the rewriter in action.\n",
        "\n",
        "First, we can go ahead an inspect the rewriter's internal tables using a `DebugView` property."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "WILDCARDS:\r\n  [l : |N, 0]\r\n\r\nLEAVES:\r\n  c => new Val(c.Value)  IF  node => (node Is Const)  (1$)\r\n\r\nCONSTANTS:\r\n  [Const(1), 4]\r\n\r\nPATTERNS:\r\n  [l, 0]\r\n  [Add(l, r), 1]\r\n  [Mul(l, r), 2]\r\n  [Add(Mul(a, b), c), 3]\r\n  [Const(1), 4]\r\n  [Add(x, Const(1)), 5]\r\n\r\nMAPS:\r\n  Add\r\n    (0, 0) --> 1\r\n    (0, 4) --> 5\r\n    (2, 0) --> 3\r\n  Mul\r\n    (0, 0) --> 2\r\n\r\nFINAL:\r\n  -2 - c => new Val(c.Value)  IF  node => (node Is Const)  (1$)\n   1 - (l, r) => new Add(l, r) --(2$)--> (l, r) => new Plus(l, r)\n   2 - (l, r) => new Mul(l, r) --(3$)--> (l, r) => new Times(l, r)\n   3 - (a, b, c) => new Add(new Mul(a, b), c) --(4$)--> (a, b, c) => new TimesPlus(a, b, c)\n   5 - x => new Add(x, new Const(1)) --(1$)--> x => new Inc(x)\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(burw.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This may look quite intimidating but it encodes the different rules in a bottom-up fashion. As a source tree is given to the rewriter, it starts by matching patterns in the rule tables starting from the leaf nodes. As it works it way up the tree, it tries to match bigger patterns and calculates the total weight of all candidate matches. When the tree is fully covered, it tries to minimize the cost by selecting the match with the lowest weight and then applies the rewrite rules. A concrete example will make this clear, by running our `arithExpr` through the rewriter."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "TimesPlus(Inc(Times(2, 3)), Times(4, 5), 6)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var numExpr = burw.Rewrite(arithExpr);\n",
        "\n",
        "Console.WriteLine(numExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we did get a tree that uses `TimesPlus` and `Inc` rather than less optimal patterns. Remember that we hooked up a logger to the rewriter, which we can now use to see the steps taken by the rewriter."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "INPUT:\r\n  Add(\r\n    Mul(\r\n      Add(\r\n        Mul(\r\n          Const(2), \r\n          Const(3)\r\n        ), \r\n        Const(1)\r\n      ), \r\n      Mul(\r\n        Const(4), \r\n        Const(5)\r\n      )\r\n    ), \r\n    Const(6)\r\n  )\r\n\r\nLABELED:\r\n  [0*, 1! (17$), 3! (16$)] Add(\r\n    [0*, 2! (14$)] Mul(\r\n      [0*, 1! (8$), 3! (7$), 5! (6$)] Add(\r\n        [0*, 2! (5$)] Mul(\r\n          [0*, -2! (1$)] Const(2), \r\n          [0*, -2! (1$)] Const(3)\r\n        ), \r\n        [0*, 4 (0$), -2! (1$)] Const(1)\r\n      ), \r\n      [0*, 2! (5$)] Mul(\r\n        [0*, -2! (1$)] Const(4), \r\n        [0*, -2! (1$)] Const(5)\r\n      )\r\n    ), \r\n    [0*, -2! (1$)] Const(6)\r\n  )\r\n\r\nRESULT:\r\n  TimesPlus(\r\n    Inc(\r\n      Times(\r\n        2, \r\n        3\r\n      )\r\n    ), \r\n    Times(\r\n      4, \r\n      5\r\n    ), \r\n    6\r\n  )\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(logger.ToString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Describing the full inner workings of BURS is outside the scope of this notebook, but suffice it to say that the labeled tree shown above shows the different rules that match each of the nodes in the tree, with an associated cost (denoted by the `$` sign representing the total cost of the rewrite). For example, the top-level node has annotations:\n",
        "\n",
        "```\n",
        "0*, 1! (17$), 3! (16$)\n",
        "```\n",
        "\n",
        "The `*` refers to a wildcard, meaning this node could be matched in a bigger parent tree. The `1!` and `3!` are final productions that correspond to using `Plus` or `TimesPlus`, as can be seen from the `DebugView` we dumped earlier. The associated costs are `17$` and `16$`, which means that the second `TimesPlus` option is cheaper, and thus the rewriter follwed that rule to rewrite the expression."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Building an optimizer\n",
        "\n",
        "BURS can also be used to write rule-driven optimizers, which are merely rewriters where the input and output languages are the same. Unlike rewriters between different languages, the rule table of an optimizer does not have to cover all possible input patterns. Instead, an optimizer can simply express some patterns it knows to optimize. To illustrate this, we'll use yet another language, called `Logic` for Boolean-valued expressions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Not(And(Not(True), Not(False)))\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using SampleTrees.Logic;\n",
        "\n",
        "var logicExpr = !(!BoolConst.True & !BoolConst.False);\n",
        "\n",
        "Console.WriteLine(logicExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Obviously this can be reduced to a single constant `true` or `false` value, but it illustrates a number of possible rewrite rules. For example, `!true` can become `false`, but a more complex pattern of the form `!(!a & !b)` can also be turned into `a | b` using De Morgan's law. Once more, we can construct a table-driven rewriter that captures various rewrite rules."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var logger = new StringWriter();\n",
        "\n",
        "var burw = new BottomUpOptimizer<LogicExpr, LogicNodeType, LogicWildcardFactory>\n",
        "{\n",
        "    // Leaf nodes\n",
        "    Leaves =\n",
        "    {\n",
        "        { (BoolConst b) => b, 1 },\n",
        "    },\n",
        "\n",
        "    Rules =\n",
        "    {\n",
        "        // Tree patterns\n",
        "        { () => !BoolConst.True, () => BoolConst.False, 1 },\n",
        "        { () => !BoolConst.False, () => BoolConst.True, 1 },\n",
        "        { p => !!p, p => p, 2 },\n",
        "\n",
        "        { p => p & BoolConst.True, p => p, 2 },\n",
        "        { p => p & BoolConst.False, p => BoolConst.False, 2 },\n",
        "        { p => BoolConst.True & p, p => p, 2 },\n",
        "        { p => BoolConst.False & p, p => BoolConst.False, 2 },\n",
        "\n",
        "        { p => p | BoolConst.True, p => BoolConst.True, 2 },\n",
        "        { p => p | BoolConst.False, p => p, 2 },\n",
        "        { p => BoolConst.True | p, p => BoolConst.True, 2 },\n",
        "        { p => BoolConst.False | p, p => p, 2 },\n",
        "\n",
        "        { (p, q) => !(!p & !q), (p, q) => p | q, 1 },\n",
        "        { (p, q) => !(!p | !q), (p, q) => p & q, 1 },\n",
        "    },\n",
        "\n",
        "    Log = logger\n",
        "};"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we have rules for negation of constants, double negation, use of `&` and `|` where one operand is a constant, but also the De Morgan rules at the bottom. Let's feed the expression from above to the rewriter and see what happens."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var optimizedLogicExpr = burw.Optimize(logicExpr);\n",
        "\n",
        "Console.WriteLine(optimizedLogicExpr);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This time, we called `Optimize` rather than `Rewrite` which keeps performing rewrites until the tree no longer changes. If we were to just call `Rewrite` (left as an exercise), we may end up with a tree that's not yet fully optimized.\n",
        "\n",
        "Let's now have a look at the rewrites that took place, by inspecting the `logger`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "INPUT:\r\n  Not(\r\n    And(\r\n      Not(\r\n        True\r\n      ), \r\n      Not(\r\n        False\r\n      )\r\n    )\r\n  )\r\n\r\nLABELED:\r\n  [4*, 5 (0$), 16! (3$)] Not(\r\n    [4*, 15 (0$)] And(\r\n      [4*, 5 (0$), 1! (1$)] Not(\r\n        [4*, 0 (0$), -2! (1$)] True\r\n      ), \r\n      [4*, 5 (0$), 3! (1$)] Not(\r\n        [4*, 2 (0$), -2! (1$)] False\r\n      )\r\n    )\r\n  )\r\n\r\nRESULT:\r\n  Or(\r\n    True, \r\n    False\r\n  )\r\n\r\nINPUT:\r\n  Or(\r\n    True, \r\n    False\r\n  )\r\n\r\nLABELED:\r\n  [4*, 13! (3$), 12! (3$)] Or(\r\n    [4*, 0 (0$), -2! (1$)] True, \r\n    [4*, 2 (0$), -2! (1$)] False\r\n  )\r\n\r\nRESULT:\r\n  True\r\n\r\nINPUT:\r\n  True\r\n\r\nLABELED:\r\n  [4*, 0 (0$), -2! (1$)] True\r\n\r\nRESULT:\r\n  True\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(logger.ToString());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can see that the rewriter was called more than once. First, our tree got rewritten using rules for Boolean negation at the leafs (`!true` became `false`, and vice versa), and the Morgan's law was applied at the top, turning the `Not(And(...))` into an `Or`. The second optimization pass was then faced with an `Or` with a `true` operand, which got ultimately reduced to `true`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Applying BURS to LINQ expression trees\n",
        "\n",
        "In order to use BURS with .NET expression trees, one has to first convert expression trees to the `ITree<T>` interface type that BURS operates on. The library comes with a `ToExpressionTree` extension method that can be used to achieve this."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "And(Constant[(bool)True](), Constant[(bool)False]())\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var expr = Expression.And(Expression.Constant(true), Expression.Constant(false));\n",
        "\n",
        "var exprTree = expr.ToExpressionTree();\n",
        "\n",
        "Console.WriteLine(exprTree);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the `ToString` representation of an `ExpressionTree` (which is an `ITree<ExpressionTreeNode>`) is a little funny looking because it rigorously prints the node's kind followed by the children in between `(` and `)`. Leaf nodes like constants have no children and end up with a `()` at the end."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Once we have an `ExpressionTree` which implements `ITree<T>` we can start to use BURS to perform rewrites, e.g. to translate an expression tree to some target language. BURS has been used to build table-driven query providers (e.g. going from expression trees to some `ITree<SqlNode>` for translation to SQL) and optimizers. Mileage varies depending on the complexity of the rule matching involved. Further extensions of BURS have been written in spin-off projects, modeling type system checks (e.g. how does a rule involving a method invocation `object.Equals(object)` relate to rules that involve an override of this virtual method on a more derived type?), supporting additional predicates to drive the rule selection process, and dynamic computation of weights."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Miscellaneous utilities\n",
        "\n",
        "In this final section of the notebook, we'll look at some remaining utilities that are provided by the library."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `ReflectionHelpers`\n",
        "\n",
        "This type provides a set of `InfoOf` methods that obtain a `MemberInfo` from an expression tree. This is a mechanism akin to `typeof` for types but targeting methods, properties, fields, and constructors instead (much like a hypothethical C# `infoof` operator could do). For example:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.String Substring(Int32, Int32)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "System.DateTime Now\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Void .ctor(Int32, Int32, Int32)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine((MethodInfo)ReflectionHelpers.InfoOf((string s) => s.Substring(0, 1)));\n",
        "Console.WriteLine((PropertyInfo)ReflectionHelpers.InfoOf(() => DateTime.Now));\n",
        "Console.WriteLine((ConstructorInfo)ReflectionHelpers.InfoOf(() => new TimeSpan(0, 0, 0)));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### `RuntimeCompiler`\n",
        "\n",
        "The runtime compiler uses `System.Reflection.Emit` to build anonymous types, closure types, and so-called record types. The resulting types are often used in expression trees. For example, one could erase nominal types (such as a `Person` type) for structurally identical types (e.g. a record containing a `string Name` and `int Age`), which then case be used to serialize types by their shape rather than by their name."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Anonymous types\n",
        "\n",
        "Runtime-generated anonymous types are analogous to C# 3.0 and VB 9.0 anonymous types. Both flavors can be built using different overloads of `CreateAnonymousType`:\n",
        "\n",
        "```csharp\n",
        "public static Type CreateAnonymousType(IEnumerable<KeyValuePair<string, Type>> properties);\n",
        "public static Type CreateAnonymousType(IEnumerable<StructuralFieldDeclaration> properties);\n",
        "\n",
        "public static Type CreateAnonymousType(IEnumerable<KeyValuePair<string, Type>> properties, params string[] keys);\n",
        "public static Type CreateAnonymousType(IEnumerable<StructuralFieldDeclaration> properties, params string[] keys);\n",
        "```\n",
        "\n",
        "Overloads with `StructuralFieldDeclaration` support adding custom attributes to the generated properties. The difference between overloads that lack a `keys` parameter versus the ones that have one has to do with the properties that participate in the implementation for `Equals` and `GetHashCode`. Being able to specify particular properties as \"keys\" matches the design of anonymous types in Visual Basic.\n",
        "\n",
        "An example is shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "<>f__AnonymousType1\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "{ Name = Bart, Age = 21 }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "{ Name = Bart, Age = 21 }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Are equal? True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var anon = RuntimeCompiler.CreateAnonymousType(new StructuralFieldDeclaration[]\n",
        "    {\n",
        "        new(\"Name\", typeof(string)),\n",
        "        new(\"Age\", typeof(int))\n",
        "    });\n",
        "\n",
        "Console.WriteLine(anon);\n",
        "\n",
        "var person1 = Activator.CreateInstance(anon, new object[] { \"Bart\", 21 });\n",
        "\n",
        "Console.WriteLine(person1);\n",
        "\n",
        "var person2 = Activator.CreateInstance(anon, new object[] { \"Bart\", 21 });\n",
        "\n",
        "Console.WriteLine(person2);\n",
        "\n",
        "Console.WriteLine($\"Are equal? {person1.Equals(person2)}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Closure types\n",
        "\n",
        "Closure types are simply classes that declare a bunch of fields. To create a closure type at runtime, use the `CreateClosureType` method:\n",
        "\n",
        "```csharp\n",
        "public static Type CreateClosureType(IEnumerable<KeyValuePair<string, Type>> fields);\n",
        "```\n",
        "\n",
        "An example is shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "<>c__DisplayClass1\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var closure = RuntimeCompiler.CreateClosureType(new KeyValuePair<string, Type>[]\n",
        "    {\n",
        "        new(\"x\", typeof(int)),\n",
        "        new(\"b\", typeof(bool))\n",
        "    });\n",
        "\n",
        "Console.WriteLine(closure);\n",
        "\n",
        "dynamic d = Activator.CreateInstance(closure);\n",
        "d.x = 42;\n",
        "d.b = true;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Record types\n",
        "\n",
        "The notion of record types in this library predates C# 9.0's record types by almost a decade, so their characteristics are quite different. Record types in this library are classes that are similar to anonymous types but provide control over the implementation of equality (value versus reference equality). Furthermore, they support assignment to properties. Use the `CreateRecordType` method to create them:\n",
        "\n",
        "```csharp\n",
        "public static Type CreateRecordType(IEnumerable<KeyValuePair<string, Type>> properties, bool valueEquality);\n",
        "public static Type CreateRecordType(IEnumerable<StructuralFieldDeclaration> properties, bool valueEquality);\n",
        "```\n",
        "\n",
        "An example is shown below:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "<>a__RecordType1\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "{ Name = Bart, Age = 21 }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "{ Name = Bart, Age = 21 }\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Are equal? True\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var record = RuntimeCompiler.CreateRecordType(new StructuralFieldDeclaration[]\n",
        "    {\n",
        "        new(\"Name\", typeof(string)),\n",
        "        new(\"Age\", typeof(int))\n",
        "    }, valueEquality: true);\n",
        "\n",
        "Console.WriteLine(record);\n",
        "\n",
        "dynamic person1 = Activator.CreateInstance(record);\n",
        "person1.Name = \"Bart\";\n",
        "person1.Age = 21;\n",
        "\n",
        "Console.WriteLine(person1);\n",
        "\n",
        "dynamic person2 = Activator.CreateInstance(record);\n",
        "person2.Name = \"Bart\";\n",
        "person2.Age = 21;\n",
        "\n",
        "Console.WriteLine(person2);\n",
        "\n",
        "Console.WriteLine($\"Are equal? {person1.Equals(person2)}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### `Define*` method variants\n",
        "\n",
        "In addition to the `Create*` methods illustrated above, variants with the `Define*` prefix are provided as well. Rather than returning a `Type`, these accept a `TypeBuilder` to define the type on. These variants are useful when trying to build recursive types (i.e. there's a cycle between declarations and uses of types), because one can use `TypeBuilder` instances for the types of the properties on the anonymous or record type being constructed. Furthermore, one could extend these types with custom members (e.g. a closure type could have instance members associated with it that operate on the state captured in fields). Once all types have been defined, the user can then call `CreateType` on the `TypeBuilder` instances. Examples of types with cycles are:\n",
        "\n",
        "```csharp\n",
        "// A -> A\n",
        "class A\n",
        "{\n",
        "    public A Next { get; set; }\n",
        "}\n",
        "\n",
        "// B -> C\n",
        "class B\n",
        "{\n",
        "    public C C { get; set; }\n",
        "}\n",
        "\n",
        "// C -> B\n",
        "class C\n",
        "{\n",
        "    public B B { get; set; }\n",
        "}\n",
        "```\n",
        "\n",
        "As an example, a structurally equivalent pair of record types for `B` and `C` could be built as follows."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "16541276\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "5663325\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "5663325\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "16541276\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.Reflection.Emit;\n",
        "\n",
        "var compiler = new RuntimeCompiler();\n",
        "\n",
        "TypeBuilder tb = compiler.GetNewRecordTypeBuilder();\n",
        "TypeBuilder tc = compiler.GetNewRecordTypeBuilder();\n",
        "\n",
        "compiler.DefineRecordType(tb, new KeyValuePair<string, Type>[] { new(\"C\", tc) }, valueEquality: false);\n",
        "compiler.DefineRecordType(tc, new KeyValuePair<string, Type>[] { new(\"B\", tb) }, valueEquality: false);\n",
        "\n",
        "Type b = tb.CreateType();\n",
        "Type c = tc.CreateType();\n",
        "\n",
        "dynamic objB = Activator.CreateInstance(b);\n",
        "dynamic objC = Activator.CreateInstance(c);\n",
        "\n",
        "objB.C = objC;\n",
        "objC.B = objB;\n",
        "\n",
        "Console.WriteLine(objB.GetHashCode());\n",
        "Console.WriteLine(objC.GetHashCode());\n",
        "Console.WriteLine(objB.C.GetHashCode());\n",
        "Console.WriteLine(objB.C.B.GetHashCode());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note we use `valueEquality` set to `false` in the example above. This avoids implementations like `Equals` and `GetHashCode` from going in a cycle. Using methods like `ToString` on cyclic types like this one is fraught with danger. If you want to exit the notebook with some fireworks, run the following cell to see why (**at your own risk**)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "Console.WriteLine(objB.ToString());"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": ".NET (C#)",
      "language": "C#",
      "name": ".net-csharp"
    },
    "language_info": {
      "file_extension": ".cs",
      "mimetype": "text/x-csharp",
      "name": "C#",
      "pygments_lexer": "csharp",
      "version": "9.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}